首页 > 代码库 > POJ 3268 Silver Cow Party （ Dijkstra ）
POJ 3268 Silver Cow Party （ Dijkstra ）
题目大意：
有N个农场每个农场要有一头牛去参加一个聚会，连接每个农场有m条路， 聚会地点是X，并且路是单向的.要求的是所有牛赶到聚会地点并且回到自己原先的农场所需要的最短时间。
题目分析：
其实就是以X为终点，求出X到其他每个点的距离， 再将图反存一下，在做一次最短路， 两次距离相加求出最长的时间。
这里是用Dijkstra写的，我们第一次用邻接矩阵写，第二次用邻接表，并且有优先队列优化
1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 using namespace std;10 #define INF 0xfffffff11 #define maxn 100512 int G[2][maxn][maxn];13 int dist[2][maxn];14 bool vis[2][maxn];15 int n, m, X;16 void Dijkstra(int Star,int End,int k)17 {18 dist[k][Star] = 0;19 20 for(int i=1; i<=n; i++)21 {22 int Min = INF, index;23 for(int j=1; j<=n; j++)24 {25 if(dist[k][j] < Min && !vis[k][j])26 Min = dist[k][j], index = j;27 }28 29 vis[k][index] = true;30 31 for(int j=1; j<=n; j++)32 {33 if(!vis[k][j])34 dist[k][j] = min(dist[k][j], dist[k][index] + G[k][index][j]);35 }36 }37 }38 void Init()39 {40 memset(vis,false,sizeof(vis));41 for(int i=0; i<=n; i++)42 {43 dist[0][i] = dist[1][i] = INF;44 for(int j=0; j<=n; j++)45 G[0][i][j] = G[0][j][i] = G[1][i][j] = G[1][j][i] = INF;46 }47 }48 49 int Slove()50 {51 int Max = 0;52 Dijkstra(X,n,0);53 Dijkstra(X,n,1);54 for(int i=1; i<=n; i++)55 {56 Max = max(dist[0][i]+ dist[1][i], Max);57 }58 return Max;59 }60 int main()61 {62 while(scanf("%d%d%d",&n,&m,&X) != EOF)63 {64 Init();65 for(int i=0; i<m; i++)66 {67 int a, b, c;68 scanf("%d%d%d",&a,&b,&c);69 G[0][a][b] = min(G[0][a][b],c);70 G[1][b][a] = min(G[1][b][a],c);71 }72 int ans = Slove();73 74 cout << ans << endl;75 }76 return 0;77 }
优先队列版本
#include <iostream>#include <cmath>#include <cstring>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>using namespace std;#define INF 0xfffffff#define maxn 1006#define min(a,b) (a<b?a:b)#define max(a,b) (a>b?a:b)struct Edge{ int e; int w; friend bool operator < (Edge n1, Edge n2) { return n1.w > n2.w; }};vector<Edge>G[2][maxn];int dist[2][maxn];bool vis[2][maxn];int n, m, X;void Dijkstra(int Star,int End,int k){ Edge P, Pn; P.e = Star; P.w = 0; dist[k][P.e] = 0; priority_queue<Edge> Q; Q.push(P); while( !Q.empty() ) { P = Q.top(); Q.pop(); if( vis[k][P.e] ) continue; vis[k][P.e] = true; int len = G[k][P.e].size(); for(int i=0; i<len; i++) { Pn.e = G[k][P.e][i].e; Pn.w = G[k][P.e][i].w + P.w; if( !vis[k][Pn.e] ) { dist[k][Pn.e] = min(dist[k][Pn.e],Pn.w); Q.push(Pn); } } }}void Init(){ memset(vis,false,sizeof(vis)); for(int i=0; i<=n; i++) { G[0][i].clear(); G[1][i].clear(); dist[0][i] = dist[1][i] = INF; }}int Slove(){ int Max = 0; Dijkstra(X,n,0); Dijkstra(X,n,1); for(int i=1; i<=n; i++) { Max = max(dist[0][i]+ dist[1][i], Max); } return Max;}int main(){ Edge P; while(scanf("%d%d%d",&n,&m,&X) != EOF) { Init(); for(int i=0; i<m; i++) { int a, b, c; scanf("%d%d%d",&a,&b,&c); P.e = b, P.w = c; G[0][a].push_back(P); P.e = a; G[1][b].push_back(P); } int ans = Slove(); cout << ans << endl; } return 0;}
POJ 3268 Silver Cow Party （ Dijkstra ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。