首页 > 代码库 > POJ1502 MPI Maelstrom Dijkstra
POJ1502 MPI Maelstrom Dijkstra
题意
给出图,从点1出发,求到最后一个点的时间。
思路
单源最短路,没什么好说的。注意读入的时候的技巧。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1000000000;
const int maxn = 110;
int n;
int edge[maxn][maxn];
int d[maxn];
bool used[maxn];
void dijkstra(int s)
{
d[s] = 0;
while(true) {
int v = -1;
for(int i = 1 ; i <= n ; i ++) {
if(!used[i]) {
if(v == -1 || d[i] < d[v]) v = i;
}
}
if(v == -1) break;
used[v] = true;
for(int i = 1 ; i <= n ; i ++) {
d[i] = min(d[i],d[v]+edge[v][i]);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
fill(d,d+maxn,INF);
memset(used,false,sizeof(used));
for(int i = 0 ; i < maxn ; i ++) {
fill(edge[i],edge[i]+maxn,INF);
edge[i][i] = 0;
}
scanf("%d",&n);
for(int i = 2 ; i <= n ; i ++) {
for(int j = 1 ; j < i ; j ++) {
int tmp;
char getit;
if(scanf("%d",&tmp))
edge[i][j] = edge[j][i] = tmp;
else scanf("%c",&getit);
}
}
dijkstra(1);
int ma = d[1];
for(int i = 2 ; i <= n ; i ++) {
ma = max(d[i],ma);
}
cout << ma << endl;
return 0;
}
POJ1502 MPI Maelstrom Dijkstra
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。