POJ-1511(堆优化版dijkstra)代码简单易懂

题目大意：求点1到其他点最短距离全部相加，然后在求第n号点到其他点最短距离全部相加

题目思路：先正向建图，然后反向建图，求两次1号点到其他点的最短距离，注意输入用scanf就不会超时

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int N  = 1e6+10;
const int INF = 0x3f3f3f3f;
int n,m;
int h[N],ne[N],w[N],idx=0,e[N];
int dist[N];
int rd[N];
int a1[N],b1[N],c1[N];
bool st[N];
typedef pair<int,int>PII;
void add(int a,int b,int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
void solve(int start) {
    memset(dist,0x3f,sizeof(dist));
    memset(st,0,sizeof(st));
    dist[start] = 0;
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push({0,start});
    while(heap.size()) {
        PII t = heap.top();
        heap.pop();
        int ver = t.second,distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i=h[ver];i!=-1;i=ne[i]) {
             int j = e[i];
             if(dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
             }
        }
    }
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        memset(h,-1,sizeof(h));
        for(int i=0;i<m;i++) {
            scanf("%d%d%d",&a1[i],&b1[i],&c1[i]);
            add(a1[i],b1[i],c1[i]);
        }
        solve(1);
        ll ans=0;
        for(int i=2;i<=n;i++) {
            ans+=dist[i];
        }
        memset(h,-1,sizeof(h));

          idx=0;
        for(int i=0;i<m;i++) {
            add(b1[i],a1[i],c1[i]);
        }
        solve(1);
          for(int i=2;i<=n;i++) {
            ans+=dist[i];
        }
        cout<<ans<<endl;
    }
	return 0;
}