http://poj.org/problem?id=1502
刷一道模板题稳定一下心情。。。
Dijkstra求单源最短路，就是输入的时候注意下，是按下三角输入的（无向图），输入字符x表示i与j不通。
可以这样输入：
if(scanf("%d",&w)) map[i][j] = map[j][i] = w;
else scanf("x");
#include<stdio.h>
#include<string.h>
const int INF = 0x3f3f3f3f; int map[][],vis[],dis[],n;
void Dijkstra()
{
int i,j;
memset(vis,,sizeof(vis));
for(i = ; i < n; i++)
dis[i] = INF;
dis[] = ; for(i = ; i < n; i++)
{
int mindis = INF,pos;
for(j = ; j < n; j++)
{
if(!vis[j] && dis[j] < mindis)
{
mindis = dis[j];
pos = j;
}
}
vis[pos] = ;
for(j = ; j < n; j++)
{
if(!vis[j] && dis[j] > dis[pos]+map[pos][j])
dis[j] = dis[pos]+map[pos][j];
}
} } int main()
{
while(~scanf("%d",&n))
{
for(int i = ; i < n; i++)
for(int j = ; j < n; j++)
map[i][j] = INF;
for(int i = ; i < n; i++)
{
for(int j = ; j < i; j++)
{
int w;
if(scanf("%d",&w)) map[i][j] = map[j][i] = w;
else scanf("x");
}
}
Dijkstra();
int max = -;
for(int i = ; i < n; i++)
{
if(dis[i] > max)
max = dis[i];
}
printf("%d\n",max);
}
return ;
}