模板
三种最短路2333
1 //dijkstra
2 void dij(int s){
3 priority_queue <pair <int,int> > q; //小根堆
4 while(!q.empty()) q.pop();
5 q.push(make_pair(0,s));
6 while(!q.empty()){
7 int u = q.top().second;
8 q.pop();
9 if(vis[u]) continue;
10 vis[u] = 1;
11 for(int i = head[u];i;i = nxt[i]){
12 int t = edge[i].tt,v = edge[i].vv;
13 if(dis[t] > dis[u] + v){
14 dis[t] = dis[u] + v;
15 q.push(make_pair(dis[t],t));
16 }
17 }
18 }
19 return;
20 }
21 //floyd
22 void floyd(int s,int t){ //s:起点,t:终点
23 for(int k = 1;k <= n;++ k){
24 for(int i = 1;i <= n;++ i){
25 for(int j = 1;j <= n;++ j){
26 f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
27 }
28 }
29 }
30 cout << f[s][t] << '
';
31 return;
32 }
33 //spfa
34 queue <int> s;
35 void spfa(int x){//x:起点
36 memset(dis,0x3f,sizeof(dis));
37 while(!s.empty()) s.pop();
38 dis[x] = 0;
39 s.push(x);
40 vis[x] = 1;
41 while(!s.empty()){
42 int u = s.front();
43 s.pop();
44 vis[u] = 0;
45 for(int i = head[u];i;i = nxt[i]){
46 int t = edge[i].tt,v = edge[i].vv;
47 if(dis[t] > dis[u] + v){
48 dis[t] = dis[u] + v;
49 if(!vis[t]){
50 s.push(t);
51 vis[t] = 1;
52 }
53 }
54 }
55 }
56 return;
57 }