201703-4 ccf 地铁修建（dijstra的灵活运用）

爱被打了一巴掌 2022-05-13 06:24 228阅读 0赞

题目链接：  
[地铁修建][Link 1]

题目大意：  
中文题，不解释啊啊！！！

解题思路：  
题目要求使得完工时间最短，因为可以同时开工，所以抽象出来就是。从1到n的多条路线中，选一条路径所经过的边中最大的边权最小（看样例就可以理解这句话了）。  
于是我们可以利用求最短路的法子来求这个最大边权最小。之前求最短路是记录1到当前节点的最短路，那我是不是可以改变一下松弛条件，dist\[i\]记录的是1节点到当前节点i所有路径中最大变权的最小值呢，然后每次往后松弛，比较一下dist\[u\]和当前边权的大小，选大的和dist\[v\]去比，不断更新dist\[v\],最后就可以得到最优解了！！！

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    const int MAXN = 1e5+7;
    
    int n,m;
    int vis[MAXN],dist[MAXN];
    
    struct node{
        int v;
        int c;
        node(int _v, int _c):v(_v),c(_c){}
        bool operator <(const node&a)const{
            return c > a.c;
        }
    };
    
    vector<node> g[MAXN];
    
    void dijstra(){
        priority_queue<node> pq;
        pq.push(node(1,0));
        dist[1] =0;
        while(!pq.empty()){
            node tmp = pq.top();
            pq.pop();
            int u = tmp.v;
            if(vis[u]) continue;
            vis[u] = 1;
            for(int i=0; i<g[u].size(); ++i){
                int v = g[u][i].v;
                int cost = g[u][i].c;
    
                if(max(cost, dist[u]) < dist[v]){
                    dist[v] = max(cost, dist[u]);
                    pq.push(node(v,dist[v]));
                }
            }
        }
    }
    
    void init(){
        for(int i=0; i<MAXN; ++i) g[i].clear();
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<MAXN; ++i) dist[i] = 0x3f3f3f3f;
    }
    
    int main(){
        init();
        cin>>n>>m;
        for(int i=0; i<m; ++i){
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            g[u].push_back(node(v,c));
            g[v].push_back(node(u,c));
        }
    
        dijstra();
    
        cout<<dist[n]<<endl;
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T54