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 的进来看看,看懂我代码应该就没问题了

Posted by mz1998 at 2017-11-09 10:31:34 on Problem 1062
#include "cstdio"
#include"iostream"
#include"cstring"
#include"cmath"
#include"queue"
#include"vector"
using namespace std;
const int maxn=105;
bool inq[maxn],vis[maxn];
int d[maxn],le[maxn];

vector <pair<int,int> >E[maxn];

int spfa(int x)
{
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        int now=q.front();
        q.pop(),inq[now]=false;
        for(int i=0;i<E[now].size();i++){
            int v=E[now][i].first;
            if(d[v]>d[now]+E[now][i].second&&vis[v]){
                d[v]=d[now]+E[now][i].second;
                if(inq[v]) continue;
                q.push(v),inq[v]=true;
            }
        }
    }
    return d[1];
}
int main()
{
    int m,n,x,y,z;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&d[i],&le[i],&x);
        for(int j=0;j<x;j++){
            scanf("%d%d",&y,&z);
            E[y].push_back(make_pair(i,z));
        }
    }
    for(int i=1;i<=n;i++){
        E[0].push_back(make_pair(i,d[i]));
        d[i]=1e9;
    }
    int ans=1e9;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=maxn;j++) d[j]=1e9;/********/
        int minle=le[i];
        memset(vis,true,sizeof vis);
        memset(inq,false,sizeof inq);
        for(int j=1;j<=n;j++){
            if(le[j]<minle||le[j]-minle>m){
                vis[j]=false;
            }
        }
        ans=min(ans,spfa(0));
    }
    printf("%d\n",ans);
}
一开始wa因为每次spfa没有让距离=1e9,就是有标注的那个地方,每次spfa是没有联系的,相当于进行了n次spfa所以每次要重新设置距离为最大值。

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