POJ1511 Invitation Cards(dijkstra+heap)

给定节点数n,和边数m,边是单向边.

问从1节点出发到2,3,...n 这些节点路程和从从这些节点回来到节点1的路程和最小值。

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <limits.h>
using namespace std;
const int maxn=1000015;
const int inf=INT_MAX;        //(INT_MAX)/3 太小 
typedef pair<int,int> p;
 
struct edge{
    int to;
    int cost;
    edge(int tto=0,int ccost=0):to(tto),cost(ccost){}
};
 
int t,n,m,x,da[maxn],db[maxn],st[maxn][3];
 
vector<edge> g[maxn];
 
void dijkstra(int s,int d[]){
    priority_queue<p,vector<p>,greater<p> >qu;//堆按照p的first（最短距离）排序，小在前 
    while(!qu.empty()) qu.pop();
    fill(d,d+maxn,inf);
    d[s]=0;
    qu.push(p(0,s));
    while(!qu.empty()){
        p temp=qu.top();
        qu.pop();
        if(temp.first>d[temp.second]) continue;//跳过更新过程中入队的非最小值 
        for(int i=0;i<g[temp.second].size();++i){
            edge e=g[temp.second][i];
            if(d[e.to]>d[temp.second]+e.cost){
                d[e.to]=d[temp.second]+e.cost;
                qu.push(p(d[e.to],e.to));
            }
        }
    }
}
 
int main(){
    int a,b,c;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;++i){
            g[i].clear();
        }
        for(int i=1;i<=m;++i){
            scanf("%d%d%d",&st[i][0],&st[i][1],&st[i][2]);
            g[st[i][0]].push_back(edge(st[i][1],st[i][2]));
        }
        dijkstra(1,da);
        for(int i=0;i<=n;++i){
            g[i].clear();
        }
        for(int i=1;i<=m;++i){
            g[st[i][1]].push_back(edge(st[i][0],st[i][2]));
        }
        dijkstra(1,db);
        __int64 ans=0;
        for(int i=1;i<=n;++i){
            ans+=da[i];
            ans+=db[i];
        }
        printf("%I64d
",ans);
    }
    return 0;
}