Question

POJ 2394 WA

简单的Dijkstra算法的。。为什么会WA呢，求助。。
#include<iostream>
using namespace std;
const int MAXPATH=10000000;

int F,P,C,M;
int map[501][501];
int dis[501],if_dis[501],flag[501];

int findmin()
{ int minnode=0,minpath=MAXPATH;
for(int i=1;i<=F;i++){
if(if_dis[i]==0&&dis[i]<minpath){
minpath=dis[i];
minnode=i;
}
}
return minnode;
}

int main()
{ int i,j;
int x,y,t;
while(scanf("%d%d%d%d",&F,&P,&C,&M)!=EOF){
for(i=1;i<=F;i++){
for(j=1;j<=F;j++)
map[i][j]=MAXPATH;
map[i][i]=0;
}
memset(if_dis,0,sizeof(if_dis));
memset(flag,0,sizeof(flag));
for(i=1;i<=P;i++){
scanf("%d%d%d",&x,&y,&t);
if(map[x][y]>t){
map[x][y]=t;
map[y][x]=t;
}
}
//Dijfstra
if_dis[1]=1;
dis[1]=0;
for(i=2;i<=F;i++)
dis[i]=map[1][i];

int done;
done=1;
while(done<F){
int node=findmin();
if(node!=0){
if_dis[node]=1;
done++;
//更新数组
for(i=1;i<=F;i++)
if(if_dis[i]==0&&dis[i]>dis[node]+map[node][i])
dis[i]=dis[node]+map[node][i];
}
else break;
}
//for(i=1;i<=F;i++)
//printf("%d ",dis[i]);
//printf("\n");
int count=0;
for(i=1;i<=C;i++){
int cow;
scanf("%d",&cow);
if(dis[cow]<=M){
flag[i]=1;
count++;
}
}
printf("%d\n",count);
for(i=1;i<=F;i++){
if(flag[i]==1)
printf("%d\n",i);
}
}
return 0;
}

Answer 1

一楼不厚道。。
我搞过ACM，你以后可以问我，分数不是问题，这个是我的代码 你参考下
顺便给你一组测试数据，这组你错了
3 2 10 4
1 2 3
3 1 10
2
2
2
2
3
3
3
2
2
2

输出应该是
7
1
2
3
4
8
9
10
你的是
7
1
2
3
--------------------------------
#include <stdio.h>
#include <vector>
#include <algorithm>
#define inf 2100000000

using namespace std;

int f, p, c, m;
int map[501][501];
int dis[501], mark[501];
vector <int> ans;

void solve()
{
int i, j, v, min;

for(i = 0; i < f; i++)
{
dis[i] = inf;
mark[i] = 0;
}
dis[0] = 0;
for(i = 0; i < f; i++)
{
min = inf;
for(j = 0; j < f; j++)
{
if(!mark[j]&&dis[j]<min)
{
min = dis[j];
v = j;
}
}
mark[v] = 1;
for(j = 0; j < f; j++)
{
if(map[v][j]&&dis[v]+map[v][j]<dis[j])
{
dis[j] = dis[v]+map[v][j];
}
}
}
}

int main()
{
int i;
int a, b, c, w;

scanf("%d%d%d%d",&f,&p,&c,&m);
memset(map,0,sizeof(map));
for(i = 0; i < p; i++)
{
scanf("%d%d%d",&a,&b,&w);
a--,b--;
if(map[a][b]==0||map[a][b]>w)
{
map[a][b] = map[b][a] = w;
}
}
solve();
for(i = 0; i < c; i++)
{
scanf("%d",&a);
a--;
if(dis[a]<=m)
{
ans.push_back(i+1);
}
}
printf("%d\n",ans.size());
for(i = 0; i < ans.size(); i++)
printf("%d\n",ans[i]);
return 0;
}

Answer 2

这里做OJ的人少, POJ的更少, 你如果真的想有人给你答案, 建议你多出十余倍的悬赏金, 或者把题目地址给出来