C - Heavy Transportation POJ - 1797————Dijkstra变形

一时失言乱红尘 2023-06-10 04:28 17阅读 0赞

https://vjudge.net/contest/313997\#problem/C

#include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    const int maxn = 1100;
    int mp[maxn][maxn];// 邻接矩阵存图
    const int inf = 0xf3f3f;
    int Dijkstra(int s, int n, int m)
    { 
        int dis[maxn];
        for(int i = 0;i <= n;i++)
        { 
            dis[i] = mp[s][i];
        }
        dis[s] = 0;
        bool vis[maxn];
        memset(vis, false, sizeof(vis));
        vis[s] = true;
    
        for(int i = 0;i < n-1;i++)
        { 
            int mx = 0;
            int u = -1;
            for(int j = 1;j <= n;j++)
            { 
                if(!vis[j]&&dis[j] > mx)// 每次找到载重量最大的
                { 
                    mx = dis[j];
                    u = j;
                }
            }
    
            if(u == -1)break;
            vis[u] = true;
            for(int j = 1;j <= n;j++)
            { 
                if(dis[j] < min(dis[u], mp[u][j]))// 通过最大站载重量 便利其他的
                { 
                    dis[j] = min(dis[u], mp[u][j]);
                }
            }
        }
        return dis[n];
    }
    void input(int n, int m)
    { 
        for(int i = 0;i < m;i++)
        { 
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            if(mp[u][v]< w)mp[u][v] = w;
            if(mp[v][u] < w)mp[v][u] = w;
        }
    }
    int main()
    { 
    
    
        int T;
        scanf("%d", &T);
        int cnt = 0;
        while(T--)
        { 
            cnt++;
            memset(mp, 0, sizeof(mp));
            int n, m;
            scanf("%d %d", &n, &m);
            input(n, m);
            int ans = Dijkstra(1, n, m);
    
            printf("Scenario #%d:\n%d\n\n",cnt, ans);
    
        }
    
    
        return 0;
    }