MPI Maelstrom(POJ1502)

题目：MPI Maelstrom

思路：用Dijkstra模板
ps:数组的范围需要注意一下，输入也需要注意一下

#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;
typedef pair<int,int>P;
const int N = 200;
const int inf = 0x3f;

struct str{
	int dot;
	int dis;
	int next;
}e[5000<<1];
int head[5000<<1];
int n;
int dis[N<<1];
int cnt = 0;

void add(int x,int y,int z){
	e[++cnt].dis = z;
	e[cnt].dot = y;
	e[cnt].next = head[x];
	head[x] = cnt;
	return;
}
int read(char s[]){
	int ans = 0;
	for(int i = 0;s[i];i++){
		ans = ans*10+s[i]-'0';
	}
	return ans;
}
void dijkstra(){
	priority_queue<P,vector<P>,greater<P> >que;
	for(int i = 1;i <= n;i++){
		dis[i] = inf;
	}
	que.push(P(0,1));
	dis[1] = 0;
	while(!que.empty()){
		P t = que.top();
		que.pop();
		int s = t.first;
		for(int i = head[t.second];i;i = e[i].next){
			int dot = e[i].dot;
			int ss = e[i].dis;
			if(s+ss < dis[dot]){
				dis[dot] = s+ss;
				que.push(P(dis[dot],dot));
			}
		}
	}
	return;
}
int solve(){
	dijkstra();
	int ans = 0;
	for(int i = 1;i <= n;i++){
	//	printf("%d ",dis[i]);
		if(dis[i] > ans && dis[i] != inf){
			ans = dis[i];
		}
	}
	return ans;
}
int main(){
	char s[20];
	scanf("%d",&n);
	int x;
	for(int i = 2;i <= n;i++){
		for(int j = 1;j < i;j++){	
			scanf("%s",s);
			if(s[0] == 'x') continue;
			int x = read(s);
			add(i,j,x);
			add(j,i,x);
		}
	}
	int ans  = solve();
	printf("%d\n",ans);
	return 0;
}