求助一道ACM题目,编译器得出正确结果但是OJ上显示Wrong Answer
题目如下:题目描述:给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。输...
题目如下:
题目描述:
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
输入:
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点t。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
------------------------------
我的代码:
#include <stdio.h>
int n,m,i,j,s,t;
int map[1010][1010];
int vi[1010];
int cost[1010][1010];
int dis[1010];
int price[1010];
const int INF = 2100000000;
void init()
{
for(i = 1; i <= n; i++)
{
vi[i] = 0;
dis[i] = INF;
price[i] = INF;
for(j = 1; j <= n; j++)
{
map[i][j] = INF;
}
}
for(i = 0; i < m ;i++)
{
int from,to,d,p;
scanf("%d%d%d%d",&from,&to,&d,&p);
map[from][to] = map[to][from] = d;
cost[from][to] = map[to][from] = p;
}
scanf("%d%d",&s,&t);
}
void dijstra()
{
dis[s] = 0;
price[s] = 0;
for(i = 1; i < n; i++)
{
int index = -1;
int minn = INF;
for(j = 1; j <= n; j++)
{
if(vi[j] == 0 && dis[j] < minn)
{
index = j;
minn = dis[j];
}
}
vi[index] = 1;
for(j = 1; j <= n; j++)
{
if(dis[j] > dis[index] + map[index][j])
{
dis[j] = dis[index] + map[index][j];
price[j] = price[index] + cost[index][j];
}else if((dis[j] == dis[index] + map[index][j]))
{
if(price[j] > price[index] + cost[index][j])
{
price[j] = price[index] + cost[index][j];
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m))
{
init();
dijstra();
printf("%d %d",dis[t],price[t]);
}
return 0;
}
为什么会错误呢 展开
题目描述:
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
输入:
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点t。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
------------------------------
我的代码:
#include <stdio.h>
int n,m,i,j,s,t;
int map[1010][1010];
int vi[1010];
int cost[1010][1010];
int dis[1010];
int price[1010];
const int INF = 2100000000;
void init()
{
for(i = 1; i <= n; i++)
{
vi[i] = 0;
dis[i] = INF;
price[i] = INF;
for(j = 1; j <= n; j++)
{
map[i][j] = INF;
}
}
for(i = 0; i < m ;i++)
{
int from,to,d,p;
scanf("%d%d%d%d",&from,&to,&d,&p);
map[from][to] = map[to][from] = d;
cost[from][to] = map[to][from] = p;
}
scanf("%d%d",&s,&t);
}
void dijstra()
{
dis[s] = 0;
price[s] = 0;
for(i = 1; i < n; i++)
{
int index = -1;
int minn = INF;
for(j = 1; j <= n; j++)
{
if(vi[j] == 0 && dis[j] < minn)
{
index = j;
minn = dis[j];
}
}
vi[index] = 1;
for(j = 1; j <= n; j++)
{
if(dis[j] > dis[index] + map[index][j])
{
dis[j] = dis[index] + map[index][j];
price[j] = price[index] + cost[index][j];
}else if((dis[j] == dis[index] + map[index][j]))
{
if(price[j] > price[index] + cost[index][j])
{
price[j] = price[index] + cost[index][j];
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m))
{
init();
dijstra();
printf("%d %d",dis[t],price[t]);
}
return 0;
}
为什么会错误呢 展开
1个回答
2016-09-18
展开全部
cost[from][to] = map[to][from] = p;
改为
cost[from][to] = cost[to][from] = p;
改为
cost[from][to] = cost[to][from] = p;
追问
这个问题改掉了 程序还是错误不能提交 方便的话 可以再给我看看吗 不胜感激 (再网上也查找了相似的程序代码能通过提交 但是自己的代码就是提交不了).另while(scanf("%d%d",&n,&m))也已经改成while(scanf("%d%d",&n,&m),n!=0 && m!=0)
追答
printf("%d %d", dis[t], price[t]);
改为
printf("%d %d\n", dis[t], price[t]);
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询