首页 > 代码库 > POJ 3268 Silver Cow Party dijkstra单源最短路
POJ 3268 Silver Cow Party dijkstra单源最短路
裸dijkstra
思路:以x为源点,求到其他点的最短路,之后把邻接矩阵转置,再求一次x源
思路:以x为源点,求到其他点的最短路,之后把邻接矩阵转置,再求一次x源
点的最短路,这样就一次是来的,一次是走的,相加迭代最大值即可
代码:
/* poj 3268 8108K 47MS */ #include<cstdio> #include<iostream> #define MAXN 1005 #define MAX_INT 2147483647 using namespace std; int gra_in[MAXN][MAXN],gra_out[MAXN][MAXN],n,m,p,dist_in[MAXN],dist_out[MAXN]; void init() { cin>>n>>m>>p; for(int i = 1;i <= m;i ++) { int a,b,c; scanf("%d %d %d",&a,&b,&c); gra_out[a][b] = c; gra_in[b][a] = c; } } void dijkstra(int gra[MAXN][MAXN] , int dist[MAXN]) { bool mark[MAXN] = {false}; for(int i = 1;i <= n;i ++) dist[i] = MAX_INT; dist[p] = 0; for(int i = 1;i <= n;i ++) { int Min = MAX_INT,tj; for(int j = 1;j <= n;j ++) { if(mark[j]) continue; if(Min > dist[j]) { Min = dist[j]; tj = j; } } mark[tj] = true; for(int j = 1;j <= n;j ++) { if(mark[j] || !gra[tj][j]) continue; dist[j] = min(dist[j] , dist[tj] + gra[tj][j]); } } } int main() { init(); dijkstra(gra_in , dist_in); dijkstra(gra_out , dist_out); int Max = 0; for(int i = 1;i <= n;i ++) Max = max(Max , dist_in[i] + dist_out[i]); cout<<Max<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。