最近发现struct板子真的好用。
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define scan(i) scanf("%d",&i) 4 #define scand(i) scanf("%lf",&i) 5 #define scanl(i) scanf("%lld",&i) 6 #define f(i,a,b) for(int i=a;i<=b;i++) 7 #define pb(i) push_back(i) 8 #define ppb pop_back() 9 #define pf printf 10 #define input freopen("in.txt","r",stdin) 11 #define output freopen("out.txt","w",stdout) 12 #define io ios::sync_with_stdio(0) 13 #define dbg(args...) cout<<#args<<" : "<<args<<endl 14 #define inf 0x3f3f3f3f 15 #define pii pair<ll, ll> 16 const int mod = 1e9+7; 17 const int maxn = 1e6+7; 18 using namespace std; 19 struct node {int to,w,next;}; 20 int n,m; 21 struct Dijkstra{ 22 ll dis[maxn]; 23 int vis[maxn]; 24 int head[maxn],cnt; 25 int s; 26 node edge[maxn]; 27 28 void init(){ 29 memset(head,-1,sizeof(head)); 30 f(i,1,n){ 31 dis[i]=2e9; 32 } 33 memset(vis,0,sizeof(vis)); 34 cnt = 0; 35 } 36 37 void add(int u,int v,int w){ 38 edge[cnt].to = v; 39 edge[cnt].w = w; 40 edge[cnt].next = head[u]; 41 head[u] = cnt++; 42 } 43 44 void dijkstra(){ 45 priority_queue<pii,vector<pii>,greater<pii> > q;//从小到大 46 dis[s] = 0; q.push({dis[s],s}); 47 while(!q.empty()){ 48 int now = q.top().second; 49 q.pop(); 50 if(vis[now]) continue; 51 vis[now] = 1; 52 for(int i = head[now]; i != -1; i = edge[i].next){ 53 int v = edge[i].to; 54 if(dis[v] > dis[now] + edge[i].w){ 55 dis[v] = dis[now] + edge[i].w; 56 q.push({dis[v],v}); 57 } 58 } 59 } 60 } 61 }dj1,dj2; 62 63 int main(){ 64 while(~scanf("%d%d",&n,&m) && n+m){ 65 dj1.init(); 66 dj2.init(); 67 for(int i = 0; i < m; i++){ 68 int u, v, w; 69 scanf("%d%d%d",&u, &v, &w); 70 dj1.add(u, v, w); 71 dj2.add(v, u, w); 72 } 73 dj1.s=1;//s起点，t终点 74 dj2.s=1;//s起点，t终点 75 dj1.dijkstra(); 76 dj2.dijkstra(); 77 ll ans=0; 78 f(i,2,n){ 79 ans+=dj1.dis[i]; 80 ans+=dj2.dis[i]; 81 } 82 printf("%lld ",ans); 83 } 84 }
2020.12.25 更新：更新了edge存储位置和int溢出问题。