为什么前三个点错

P1342 请柬

Tankoldable @ 2017-08-21 20:23:05

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
long long n,m,tot,h1[1000005],h2[1000005],dis[1000005],u[1000005],ans;
struct cmp{
    bool operator() (int a,int b) 
    {
        return dis[a]>dis[b];
    }
};
priority_queue<int ,vector<int>,cmp>q;
struct date{
    long long si,len,ne;
}line[2000005];
int main()
{   
    cin>>n>>m;
    long long a,b,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        line[++tot].si=b;
        line[tot].len=c;
        line[tot].ne=h1[a];
        h1[a]=tot;
        line[++tot].si=a;
        line[tot].len=c;
        line[tot].ne=h2[b];
        h2[b]=tot;
    }
    for(int i=1;i<=n;i++) dis[i]=200000000000000;
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int k=q.top();
        q.pop();
        if(u[k]) continue; 
        u[k]=1;
        for(int i=h1[k];i;i=line[i].ne)
        if(dis[k]+line[i].len<dis[line[i].si])
        {
            dis[line[i].si]=dis[k]+line[i].len;
            q.push(line[i].si); 
        }
    }
    for(int i=1;i<=n;i++) ans+=dis[i];
    for(int i=1;i<=n;i++) dis[i]=200000000000000;
    memset(u,0,sizeof(u));
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int k=q.top();
        q.pop();
        if(u[k]) continue; 
        u[k]=1;
        for(int i=h2[k];i;i=line[i].ne)
        if(dis[k]+line[i].len<dis[line[i].si])
        {
            dis[line[i].si]=dis[k]+line[i].len;
            q.push(line[i].si); 
        }
    }
    for(int i=1;i<=n;i++) ans+=dis[i];
    printf("%lld",ans);
    return 0;
}

|