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