迪杰斯特拉模板题（迪杰斯特拉模板）

题目连接 : https://vjudge.net/contest/280347#problem/D

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct w_W{
    ll start;
    ll eend;
    ll weight;
}edge;
typedef struct W_w{
    ll eend;
    ll weight;
    ll next;
}miao;
miao x[1000010];
edge y[1000010];
ll head[1000010];
ll cnt;
void add(ll a,ll b,ll c){
    x[cnt].eend=b;
    x[cnt].weight=c;
    x[cnt].next=head[a];
    head[a]=cnt++;
}
typedef struct W_W{
    ll num;
    ll a;
}wang;
wang foot[1000010];
bool vis[1000010];
priority_queue<wang> q1;
bool operator < (wang a ,wang b){
    return a.a>b.a;
}
ll m,n,ans;
void djstl(){
    foot[1].a=0;
    q1.push(foot[1]);
    while(q1.size()){
        ll dang=q1.top().num;
        ll money=q1.top().a;
        q1.pop();
        if(vis[dang]) continue;
        vis[dang]=true;
        for(ll i=head[dang];i!=-1;i=x[i].next){
            ll to=x[i].eend;
            if(foot[to].a==-1){
                foot[to].a=money+x[i].weight;
                 q1.push(foot[to]);
            }
            else if(foot[to].a>money+x[i].weight){
                foot[to].a=money+x[i].weight;
                 q1.push(foot[to]);
            }
        }
    }
    for(ll i=1;i<=m;i++){
        ans+=foot[i].a;
    }
}
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld %lld",&m,&n);
        memset(head,-1,sizeof(head));
        for(ll i=0;i<=m;i++){
            foot[i].num=i;
            foot[i].a=-1;
        }
        for(ll i=0;i<n;i++){
            scanf("%lld %lld %lld",&y[i].start,&y[i].eend,&y[i].weight);
            add(y[i].start,y[i].eend,y[i].weight);
        }
        memset(vis,false,sizeof(vis));
        //vis[1]=true;
        ans=0;
        djstl();
        //printf("%lld
",ans);
        memset(head,-1,sizeof(head));
        for(ll i=0;i<=m;i++){
            foot[i].num=i;
            foot[i].a=-1;
        }
        cnt=0;
        memset(vis,false,sizeof(vis));
        //vis[1]=true;
        for(ll i=0;i<n;i++){
            add(y[i].eend,y[i].start,y[i].weight);
        }
        djstl();
        printf("%lld
",ans);
    }
    return 0;
}