E - Currency Exchange——最短路_spfa()算法

向右看齐 2022-06-12 05:58 199阅读 0赞

Think:  
1知识点：最短路\_spfa()算法+前向星  
2反思：判断环是否存在

[建议参考题意分析][Link 1]

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 104;
    const int M = 104;
    
    int n, cnt, head[N], cont[N], vis[N];
    double val, dis[N];
    
    struct Edge{
        int v, next;
        double rate, comm, w;
    }edge[M*2];
    
    void add_edge(int u, int v, double r, double c);
    bool spfa(int x);
    
    int main(){
        int m, x, i, u, v;
        double r1, r2, c1, c2;
        while(~scanf("%d %d %d %lf", &n, &m, &x, &val)){
            cnt = 0;
            memset(head, -1, sizeof(head));
            for(i = 1; i <= m; i++){
                scanf("%d %d %lf %lf %lf %lf", &u, &v, &r1, &c1, &r2, &c2);
                add_edge(u, v, r1, c1);
                add_edge(v, u, r2, c2);
            }
            if(spfa(x))
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }
    void add_edge(int u, int v, double r, double c){
        edge[cnt].v = v;
        edge[cnt].w = 0;
        edge[cnt].rate = r;
        edge[cnt].comm = c;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
    bool spfa(int x){
        queue <int> q;
        memset(dis, 0, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dis[x] = val, vis[x] = 1;
        q.push(x);
        cont[x]++;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for(int i = head[u]; ~i; i = edge[i].next){
                int v = edge[i].v;
                edge[i].w = (dis[u]-edge[i].comm)*edge[i].rate - dis[u];
                if(dis[v] < dis[u] + edge[i].w){
                    dis[v] = dis[u] + edge[i].w;
                    if(!vis[v]){
                        vis[v] = 1;
                        q.push(v);
                        cont[v]++;
                    }
                    if(cont[v] >= n)/*判断是否存在环*/
                        return true;
                }
            }
        }
        return false;
    }

[Link 1]: http://blog.csdn.net/u012860063/article/details/38412685
[vjudge]: https://vjudge.net/contest/163006#problem/E