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<stdio.h>
#include<cstring>
#include<queue>
#define MAXN 100002
using namespace std; 
struct Edge
{
        int v,l,next;
}edge[MAXN*20];
int _next[MAXN],En,dis[MAXN];
queue<int> Q;
bool inQ[MAXN];
void addedge(int u,int v,int l)
{
        edge[++En].next=_next[u],_next[u]=En;
        edge[En].v=v,edge[En].l=l;
}
int SPFA(int s,int t)
{
        int u,v,l,k;
        memset(inQ,false,sizeof(inQ));
        memset(dis,0x7f,sizeof(dis));
        Q.push(s),dis[s]=0;
        while (Q.size())
        {
                u=Q.front(),inQ[u]=false,Q.pop();
                for (k=_next[u];k;k=edge[k].next)
                {
                         v=edge[k].v,l=edge[k].l;
                         if (dis[v]-dis[u]<=l) continue;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX