该楼层疑似违规已被系统折叠隐藏此楼查看此楼
//运筹学之最短路径
#include
#include
#defineM99999
intmain()
{
intG[100][100];
intn;
intp[100],flag[100],s[100];
intcur;
intm,k,l,i,j;
ifstreamfin("in.txt");
//enter
fin>>n;
for(i=0;i
for(j=0;j
G[i][j]=M;
for(i=0;i
{
fin>>m;
for(j=0;j
{
fin>>k>>l;
G[i][k-1]=l;
}
}
for(i=0;i
{
flag[i]=0;
s[i]=M;
}
cur=0;
flag[cur]=1;
s[cur]=0;
p[cur]=0;
for(i=1;i
{
for(j=0;j
{
if(flag[j]==0)
{
m=s[cur]+G[cur][j];
if(m
{
s[j]=m;
p[j]=cur;
}
}
}
m=M;
for(j=0;j
{
if(flag[j]==0)
{
if(s[j]
{
m=s[j];
cur=j;
}
}
}
flag[cur]=1;
if(s[cur]==M)
{
//continue;
p[cur]=0;
for(j=0;j
if(flag[j]==0)
{
s[j]=M;
p[j]=0;
flag[j]=1;
}
break;
}
}
ofstreamfout("out.txt");
for(i=1;i
{
if(s[i]==M)
{
cout<
fout<
}
else
{
cout<
cout<
fout<
fout<
k=p[i];
cout<
fout<
while(k!=0)
{
k=p[k];
cout<
fout<
}
}
cout<
fout<
}
return0;
}
测试数据：
11
22248
25146
27911
137
29145
3534174
34793101
252119
26687
291114
192
11表示有11个顶点的图
22248
2表示第一个顶点射出2条线，22表示1->2的长度为2。。。。。。。。
输出数据:
从第1个点到第2的最短路为:2.
路径为:2
从第1个点到第3的最短路为:15.
路径为:3
从第1个点到第4的最短路为:8.
路径为:4
从第1个点到第5的最短路为:3.
路径为:5
从第1个点到第6的最短路为:10.
路径为:6
从第1个点到第7的最短路为:14.
路径为:7
从第1个点到第8的最短路为:11.
路径为:8
从第1个点到第9的最短路为:4.
路径为:9
从第1个点到第10的最短路为:15.
路径为:10
从第1个点到第11的最短路为:19.
路径为:11
