RE求助

P1342 请柬

Seauy @ 2019-08-18 17:58:27

程序为何未响应啊QAQ 查了半天错都没看出来

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1000000;

struct DE {int nxt,val;};

int n;
vector<DE> edge[2][MAXN+5];

void Build(int a,int b,int v)
{
    edge[0][a].push_back(DE{b,v});
    edge[1][b].push_back(DE{a,v});
}

long long SPFA(int start,bool D)
{
    //cout<<1<<endl;
    bool inQ[MAXN+5];
    long long dis[MAXN+5];
    queue<int> Q;
    memset(inQ,0,sizeof inQ);
    for(int i=1;i<=n;i++) dis[i]=(LONG_MAX/2)*(i!=start);
    Q.push(start);
    while(!Q.empty())
    {
        int now=Q.front();Q.pop();
        inQ[now]=0;
        for(int i=0;i<edge[D][now].size();i++)
        {
            int rear=edge[D][now][i].nxt;
            int cost=edge[D][now][i].val;
            if(dis[rear]>dis[now]+cost)
            {
                dis[rear]=dis[now]+cost;
                if(!inQ[rear])
                {
                    inQ[rear]=1;
                    Q.push(rear);
                }
            }
        }
    }
    long long cnt=0;
    for(int i=1;i<=n;i++) cnt+=dis[i];
    return cnt;
}

int main()
{
    int m;
    scanf("%d %d",&n,&m);
    while(m--)
    {
        int a,b,v;
        scanf("%d %d %d",&a,&b,&v);
        Build(a,b,v);
    }
    //cout<<1<<endl;
    printf("%lld\n",SPFA(1,0)+SPFA(1,1));
    return 0;
}

by Seauy @ 2019-08-18 18:04:03

看来是我计算机炸了 QAQ 过都过了,本地还给我停止运行


|