1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define Maxn 2000000
using namespace std;
int fir[Maxn],nex[Maxn],dis[Maxn],to[Maxn],c[Maxn];
bool inq[Maxn];
queue<int> q;
int tot,n,m,s,t;
void addedge(int x,int y,int z){
    to[++tot]=y;
    c[tot]=z;
    nex[tot]=fir[x];
    fir[x]=tot;
}
void add(int x,int y,int z) {
    addedge(x,y,z);
    addedge(y,x,z);
}
int spfa() {
    dis[s]=0;
    q.push(s); inq[s]=1;
    while (!q.empty()){
        int x=q.front();
        q.pop(), inq[x]=0;
        for (int u=fir[x]; u; u=nex[u]){
            int v=to[u];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX