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 <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define Maxn 105000
#define Maxm 1000500
#define INF 0x3f3f3f3f
struct Edge{
    int to;int len;
    int next;
}edge[Maxm*2];
int en,head[Maxn];
inline void add_edge(int u,int v,int len){
    edge[en].to=v;edge[en].len=len;edge[en].next=head[u];head[u]=en++;
}
int dis[Maxn];
bool vis[Maxn];
int spfa(int src,int des){
    memset(vis,false,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    queue<int> que;
    que.push(src);vis[src]=true;dis[src]=0;
    while (!que.empty()){
        int u=que.front();que.pop();vis[u]=false;
        for (int p=head[u];~p;p=edge[p].next){
            int v=edge[p].to,len=edge[p].len;
            if (dis[v]>dis[u]+len){
                dis[v]=dis[u]+len;
                if (!vis[v]){
                    que.push(v);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX