首页 > 代码库 > poj3268
poj3268
题目链接:https://vjudge.net/problem/POJ-3268
解题思路:各牛从farm #X回家的最短路很容易求,用Dijkstra求X到各点的单源最短路即可。难点在于求各牛从家到X点的最短路,因为路是单向的,所以往返的最短路未必相等。在这点有一个很巧妙的解决思路:把已知的各单向路倒置,权值不变,再用一次Dijkstra,此时的X到各点的单源最短路其实就是各点到X的最短路。
AC代码:
#include <iostream> #include <cstdio> using namespace std; int len[1005][1005],dlen[1005][1005]; int vis[1005],d[1005],dvis[1005],dd[1005]; const int INF=1e8; int main() { int N,M,X; scanf("%d%d%d",&N,&M,&X); for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ if(i==j) len[i][j]=len[j][i]=dlen[i][j]=dlen[j][i]=0; else len[i][j]=len[j][i]=dlen[i][j]=dlen[j][i]=INF; } d[i]=dd[i]=INF; } d[X]=dd[X]=0; while(M--){ int a,b,t; scanf("%d%d%d",&a,&b,&t); len[a][b]=dlen[b][a]=t; } while(1){ int v=-1; for(int u=1;u<=N;u++){ if(!vis[u] && (v==-1||d[u]<d[v])) v=u; } if(v==-1) break; vis[v]=1; for(int u=1;u<=N;u++) d[u]=min(d[u],d[v]+len[v][u]); } while(1){ int v=-1; for(int u=1;u<=N;u++){ if(!dvis[u] && (v==-1||dd[u]<dd[v])) v=u; } if(v==-1) break; dvis[v]=1; for(int u=1;u<=N;u++) dd[u]=min(dd[u],dd[v]+dlen[v][u]); } int ans=0; for(int i=1;i<=N;i++){ if(dd[i]+d[i]>ans) ans=dd[i]+d[i]; } printf("%d\n",ans); return 0; }
poj3268
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。