poj3268 Silver Cow Party(最短路)
发布时间:2020-12-14 04:45:59 所属栏目:大数据 来源:网络整理
导读:非常感谢kuangbin专题啊,这道题一开始模拟邻接表做的,反向边不好处理,邻接矩阵的话舒服多了。 题意:给n头牛和m条有向边,每头牛1~n编号,求所有牛中到x编号去的最短路+回来的最短路的最大值。 #include iostream #include cstring #include cstdio #incl
非常感谢kuangbin专题啊,这道题一开始模拟邻接表做的,反向边不好处理,邻接矩阵的话舒服多了。 题意:给n头牛和m条有向边,每头牛1~n编号,求所有牛中到x编号去的最短路+回来的最短路的最大值。 #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,sizeof(vis) ); memset( dis2,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,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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |