洛谷 UVA721 Invitation Cards（set优化dijkstra）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxm=1000005;
 4 int t,n,m,cnt[2],p[2][maxm];
 5 int dis[2][maxm];
 6 set<pair<int,int> > q; 
 7 struct node{
 8     int v,next,value;
 9 }e[2][maxm];
10 void insertt(int id,int u,int v,int value){
11     cnt[id]++;
12     e[id][cnt[id]].v=v;
13     e[id][cnt[id]].next=p[id][u];
14     e[id][cnt[id]].value=value;
15     p[id][u]=cnt[id];
16 }
17 void dij(int id){
18     q.clear();
19     dis[id][1]=0;
20     q.insert(make_pair(0,1));
21     while(!q.empty()){
22         int u=q.begin()->second;
23         q.erase(q.begin());
24         for(int i=p[id][u];i!=-1;i=e[id][i].next){
25             int v=e[id][i].v,value=e[id][i].value;
26             if(dis[id][v]>dis[id][u]+value){
27                 q.erase(make_pair(dis[id][v],v));
28                 dis[id][v]=dis[id][u]+value;
29                 q.insert(make_pair(dis[id][v],v));
30             }
31         }
32     }
33 }
34 int main(){
35     cin>>t;
36     while(t--){
37         memset(p,-1,sizeof(p));
38         memset(dis,0x3f,sizeof(dis));
39         memset(e,0,sizeof(e));
40         memset(cnt,0,sizeof(cnt));
41         scanf("%d%d",&n,&m);
42         for(int i=1;i<=m;i++){
43             int u,v,value;
44             scanf("%d%d%d",&u,&v,&value);
45             insertt(0,u,v,value);
46             insertt(1,v,u,value);
47         }
48         long long ans=0;
49         dij(0);
50         dij(1);
51         for(int id=0;id<=1;id++){
52             for(int i=1;i<=n;i++){
53                 ans+=dis[id][i];
54             }
55         }
56         printf("%lld\n",ans);
57     }
58     return 0;
59 }