和GG一起回家
时间限制(普通/Java):1000MS/5000MS 运行内存限制:65536KByte
总提交:288 测试通过:125
描述
今天是周末，MM想回家休息，当然GG自然就成了护花使者^_^
小镇上共有N个路口，学校在路口1旁，MM的家在路口N，路口之间有道路相连.GG希望早点送MM到家（那样他可以在家里多坐会。。。），所以他希望回家的路径最短。这需要你的帮助。
输入
多组数据。对于每组数据，第一行为一个整数，N（1<=N<=100)。接下来N行每行N个整数，第 i 行第 j 个数表示路口i和路口j之间的距离。
输出
对于每组数据，输出一个整数，从路口1到路口N的最短路径。
样例输入
3
0 2 10
2 0 1
10 1 0
样例输出
3
提示
最短路
题目来源
Narashy、xFengChenx
分析 用的
Dijkstra算法不过效率不高
#include <stdio.h>//Dijkstra
#define max 9999
int d[100],w[100][100],q[100];
void relax(int u,int v)
{
if (u==v)
{
return;
}
if (d[v]>d[u]+w[u][v])
{
d[v]=d[u]+w[u][v];
}
}
int min_Q(int n)
{
int i,_min=max,j=-1;
for (i=0;i<n;i++)
{
if(_min>d[i]&&q[i]==0)
{
_min=d[i];
j=i;
}
}
return j;
}
int main()
{
int n,m,k,i,j;
while ( scanf("%d",&n)!=EOF)
{
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
scanf("%d",&w[i][j]);
}
d[i]=max;
q[i]=0;
}
d[0]=0;
while (min_Q(n)!=-1)
{
k=min_Q(n);
q[k]=1;
for (i=0;i<n;i++)
{
relax(k,i);
}
}
printf("%d\n",d[n-1]);
}
}