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 <cstring>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
int position[100001];
int dist[100001];
vector<pair<int,int> > graph[100001];
queue<int> sque;
int N,M,S,T;                                
void spfa(){
    sque.push(S);
    position[S] = 0;
    dist[S] = 0;
    while(!sque.empty()){
        int nodeU = sque.front();
        for(int i = 0; i < graph[nodeU].size(); i++){
            int nodeV = graph[nodeU][i].first;
            int temp = dist[nodeU] + graph[nodeU][i].second;
            if(dist[nodeV] == -1 || temp < dist[nodeV]){
                dist[nodeV] = temp;
                if(position[nodeV] == -1){
                    sque.push(nodeV);
                    position[nodeV] = sque.size() - 1;
                }
            }
        }
        sque.pop();
        position[nodeU] = -1;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX