Question

一道关于最短路径的题目ACM C语言

#include<stdio.h>
#define infinity 1000001
#define len 1009
int main(){
int i,j,t,n,m,d,p,v,f,map[len][len],s[len],dist[len],distm[len],mapm[len][len];
while(scanf("%d%d",&n,&m)!=EOF,n!=0||m!=0){
for(i=0;i<len;i++)
for(j=0;j<len;j++)
map[i][j]=infinity,mapm[i][j]=infinity;
for(t=1;t<=m;t++){
scanf("%d%d%d%d",&i,&j,&d,&p);
if(map[i][j]>d)
map[j][i]=map[i][j]=d,mapm[j][i]=mapm[i][j]=p;
}
scanf("%d%d",&v,&f);
for(j=1;j<=n;j++){
s[j]=1;
dist[j]=map[v][j],distm[j]=mapm[v][j];
}
dist[v]=0;
s[v]=0;
int u,min;
for(i=1;i<=n;i++){
min=infinity;
for(j=1;j<=n;j++)
if(s[j]&&dist[j]<min)
min=dist[j],u=j;
if(min==infinity) break;
s[u]=0;
for(j=1;j<=n;j++)
if(s[j]){
if(dist[u]+map[u][j]<dist[j]){
dist[j]=dist[u]+map[u][j];
distm[j]=distm[u]+mapm[u][j];
}
else if(dist[u]+map[u][j]==dist[j]&&(distm[u]+mapm[u][j]<distm[j]))
distm[j]=distm[u]+mapm[u][j];

}
}
printf("%d %d\n",dist[f],distm[f]);
}
}
题目
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
输出 一行有两个数， 最短距离及其花费
3 2
1 2 5 6
2 3 4 5
1 3
0 0

9 11
题目是HDOJ上的3790 不知道为什么会RUNTIME ERROR

Answer 1

你这个程序写得让人生气。变量太多了，中间还没printf语句提示输入，注释一个也没有
代码书写可读性太差了。花好大力气把你变量干什么搞清楚啦，可是我都懒得去想你那程序中心代码为啥错啦。最短路径就是地杰斯特拉算法，我也不太熟，你自己好好揣摩吧。
#include<stdio.h>
#define infinity 10000
#define len 100
int main()
{
int i,j,t,num,row,d,cost;
int v,f;
int map[len][len],s[len],dist[len],distm[len],mapm[len][len];
while(scanf("%d%d",&num,&row)!=EOF && num!=0 && row!=0)
{
for(i=0;i<len;i++)
for(j=0;j<len;j++)
{
map[i][j]=infinity;
mapm[i][j]=infinity;
}
printf("input the infor:\n");
for(t=1;t<=row;t++)
{
scanf("%d %d %d %d",&i,&j,&d,&cost);
if(map[i][j]>d)
{
map[j][i]=map[i][j]=d;
mapm[j][i]=mapm[i][j]=cost;
}
}
printf("input the two node:\n");
scanf("%d %d",&v,&f);
for(j=1;j<=num;j++) //initialize
{
s[j]=1;
dist[j]=map[v][j];
distm[j]=mapm[v][j];
}
dist[v]=0;
s[v]=0;
int u,min;
for(i=1;i<=num;i++)
{
min=infinity;
for(j=1;j<=num;j++)
if(s[j] && dist[j]<min)
{
min=dist[j];
u=j; //u to record the minimum
}
if(min==infinity) break;
s[u]=0;
for(j=1;j<=num;j++)
if(s[j])
{
if(dist[u]+map[u][j]<dist[j])
{
dist[j]=dist[u]+map[u][j];
distm[j]=distm[u]+mapm[u][j];
}
else if(dist[u]+map[u][j]==dist[j]&&(distm[u]+mapm[u][j]<distm[j]))
distm[j]=distm[u]+mapm[u][j];

}
}
printf("%d %d\n",dist[f],distm[f]);
}
}

Answer 2

拿你的代码做了实验，后面的全部注释掉，只留数组定义那一行就通不过
应该是大数组的堆栈溢出问题，你定义的数组1009*1009*4=4M，vc默认栈超过1M就完蛋啊
用动态的吧，还省内存空间
后面的代码问题也不少，比如路径长度和权重的赋值，明显出了问题，下标是要减一的。之后的没看，先解决这些再说吧