poj3268 Silver Cow Party（最短路）

素颜马尾好姑娘i 2021-10-29 16:22 152阅读 0赞

非常感谢kuangbin专题啊，这道题一开始模拟邻接表做的，反向边不好处理，邻接矩阵的话舒服多了。

题意：给n头牛和m条有向边，每头牛1~n编号，求所有牛中到x编号去的最短路+回来的最短路的最大值。

![1682883-20190527185439037-1445749065.png][]

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    const int maxn = 1e3 + 5;
    const int maxm = 1e5 + 5;
    const int inf = 0x3f3f3f3f;
    struct edge{
        int s, to, w, next;
    } ed[maxm];
    int n, m, x;
    int mp[maxn][maxn], dis1[maxn], dis2[maxn];
    bool vis[maxn];
    inline int max( int a, int b ){
        return a>b ? a:b;
    }
    
    inline int min( int a, int b ){
        return a<b ? a:b; 
    }
    
    inline int dij(){
        //先求了去到x的最短路
        memset( vis, 0, sizeof(vis) );
        memset( dis1, inf, sizeof(dis1) );
        dis1[x] = 0;
        for( int i=1; i<n; i++ ){
            int minid, MIN=inf;
            for( int j=1; j<=n ;j++ ) if( !vis[j] && MIN>dis1[j] ) MIN = dis1[minid=j];
            vis[minid] = 1;
            for( int j=1; j<=n; j++ ) if( !vis[j] ) dis1[j] = min(dis1[j], dis1[minid]+mp[minid][j]);
        }
        //接下来求回去的最短路
        memset( vis, 0, sizeof(vis) );
        memset( dis2, inf, sizeof(dis2) );
        dis2[x] = 0;
        for( int i=1; i<n; i++ ){
            int minid, MIN = inf;
            for( int j=1; j<=n; j++ ) if( !vis[j] && MIN>dis2[j] ) MIN = dis2[minid=j];
            vis[minid] = 1;
            for( int j=1; j<=n; j++ ) if( !vis[j] ) dis2[j] = min( dis2[j], dis2[minid]+mp[j][minid] );
        }
        //遍历求出res
        int res = -inf;
        for( int i=1; i<=n; i++ ) res = max( dis1[i]+dis2[i], res );
        return res;
    }
    
    int main(){
        // freopen("in.txt", "r", stdin);
        ios::sync_with_stdio(0);    //加速cin 和 cout读取速度，但是这样的话就不能使用scanf了
        cin.tie(0);
        cout.tie(0);
        cin >> n >> m >> x;
        memset( mp, inf, sizeof(mp) );
        for( int i=1; i<=n; i++ ) mp[i][i] = 0;
        for( int i=0; i<m; i++ ){
            int u, v, w;
            cin >> u >> v >> w;
            mp[u][v] = w;
        }
        cout << dij() << endl;
    
        return 0;
    }

转载于:https://www.cnblogs.com/WAautomaton/p/10932409.html

[1682883-20190527185439037-1445749065.png]: /images/20211029/4d363fcbba30427a8fee65fdbb822fbc.png