| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
高手们能帮小弟看看程序为什么WA吗?我跟踪每步都是对的,但还是WA?是不是有什么边缘数据或变态数据?#include <iostream>
#include <vector>
#include <memory>
#include <cstdio>
using namespace std;
vector<int> array[501],unso,re;
long len[501][501],location[101];
int F,P,C,M;
void check(int x)
{
int i,n=array[x].size(),min=100000001,j;
for(i=0;i<n;i++)
{
if(len[1][array[x][i]]>(len[1][x]+len[x][array[x][i]]))
{
len[1][array[x][i]]=(len[1][x]+len[x][array[x][i]]);
// cout<<array[x][i]<<' '<<len[1][array[x][i]];
// system("PAUSE");
}
// cout<<array[x][i]<<' '<<x<<' '<<len[1][array[x][i]]<<' ';
// system("PAUSE");
}
// if(len[1][x]<=M&&location[x]!=0)
// re.push_back(location[x]);
n=unso.size();
j=0;
if(n!=0)
{
for(i=0;i<n;i++)
{
if(min>len[1][unso[i]])
{
j=i;
min=len[1][unso[i]];
// cout<<unso[i]<<' '<<len[1][unso[i]]<<' ';
// system("PAUSE");
}
}
n=unso[j];
// cout<<unso[j];
// system("PAUSE");
unso.erase(unso.begin()+j);
check(n);
}
}
int main()
{
int i,j,min;
while(scanf("%d%d%d%d",&F,&P,&C,&M)!=EOF)
{
int a,b,c;
re.clear();
for(i=0;i<F+1;i++)
for(j=0;j<F+1;j++)
len[i][j]=100000000;
len[1][1]=0;
memset(location,0,sizeof(location));
unso.clear();
array[1].clear();
for(i=2;i<F+1;i++)
{
unso.push_back(i);
array[i].clear();
}
for(i=0;i<P;i++)
{
scanf("%d%d%d",&a,&b,&c);
array[a].push_back(b);
array[b].push_back(a);
len[a][b]=c;
len[b][a]=c;
}
for(i=1;i<=C;i++)
{
scanf("%d",&a);
location[i]=a;
}
check(1);
for(i=1;i<C+1;i++)
{
if(len[1][location[i]]<=M)
re.push_back(i);
}
int n=re.size();
cout<<n<<endl;
if(n==0)
{
cout<<0<<endl;
continue;
}
sort(re.begin(),re.end());
int f=0;
for(i=0;i<n;i++)
{
cout<<re[i]<<endl;
f=1;
}
if(f==0&&n!=0)
cout<<0<<endl;
}
return 0;
}
/*
7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7
*/
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator