Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

高手们能帮小弟看看程序为什么WA吗?我跟踪每步都是对的,但还是WA?是不是有什么边缘数据或变态数据?

Posted by rabbit0404 at 2006-07-25 19:56:38 on Problem 2394
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator