[kuangbin带你飞]专题四 最短路练习 J POJ 1511

题目地址：https://vjudge.net/contest/66569#problem/J

思路：数据量比较大的题目。我一开始用vector建图，TLE成傻逼，加了输入挂也过不去……然后默默改成用邻接表就过了，这莫非是故意卡STL？话说这题有个坑，这题的数据更改过，现在有数据会超int，于是我索性就全开了longl ong。（蜜汁WA两次之后去讨论版才看到……）

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define INF 1e17
using namespace std;
const int maxn=1e6+5;
struct pos
{
    int u,v,w,next;
} E1[maxn];
pos E2[maxn];
int head1[maxn];
int head2[maxn];
long long d[maxn];
int p,q;
int k1;
int k2;
template <typename T>
inline void read(T& x)
{
    char ch;
    while (!((((ch=getchar())>='0') && (ch <= '9')) || (ch == '-')));
    x = ch-'0';
    while (((ch=getchar())>='0') && (ch <= '9')) x = x*10+ch-'0';
}

void dij2(int s)
{
    for(int i=0; i<=p; i++)
    {
        d[i]=INF;
    }
    priority_queue<pair<long long,int> >q;
    d[s]=0;
    q.push(make_pair(-d[s],s));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        for(int i=head2[now]; i!=-1; i=E2[i].next)
        {
            int v=E2[i].v;
            if(d[v]>d[now]+E2[i].w)
            {
                d[v]=d[now]+E2[i].w;
                q.push(make_pair(-d[v],v));
            }
        }
    }
}

void dij1(int s)
{
    for(int i=0; i<=p; i++)
    {
        d[i]=INF;
    }
    priority_queue<pair<long long,int> >q;
    d[s]=0;
    q.push(make_pair(-d[s],s));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        for(int i=head1[now]; i!=-1; i=E1[i].next)
        {
            int v=E1[i].v;
            if(d[v]>d[now]+E1[i].w)
            {
                d[v]=d[now]+E1[i].w;
                q.push(make_pair(-d[v],v));
            }
        }
    }
}


void addedge1(int u,int v,int w)
{
    E1[++k1].u=u;
    E1[k1].v=v;
    E1[k1].w=w;
    E1[k1].next=head1[u];
    head1[u]=k1;
}

void addedge2(int u,int v,int w)
{
    E2[++k2].u=u;
    E2[k2].v=v;
    E2[k2].w=w;
    E2[k2].next=head2[u];
    head2[u]=k2;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int casei=1; casei<=t; casei++)
    {
        read(p);
        read(q);
        memset(head1,-1,sizeof(head1));
        memset(head2,-1,sizeof(head2));
        k1=k2=0;
        for(int i=0; i<q; i++)
        {
            int a,b,c;
            read(a);
            read(b);
            read(c);
            addedge1(a,b,c);
            addedge2(b,a,c);
        }
        long long ans=0;
        dij1(1);
        for(int i=2; i<=p; i++)
            ans+=d[i];
        dij2(1);
        for(int i=2; i<=p; i++)
            ans+=d[i];
        printf("%I64d\n",ans);
    }
}