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 <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
struct EDGE{
    int to,w;
    struct EDGE* next;
}e[2000010];
struct EDGE* p[100010]={0};
int dis[100010],size=0;
queue<int> h;
bool is[100010]={false};
void addedge(int a,int b,int c)
{
    e[size].to=b;e[size].w=c;
    e[size].next=p[a];p[a]=&e[size];
    size++;
}
void bfs(int s)
{
    dis[s]=0;is[s]=0;
    h.push(s);
    while(!h.empty()){
        int f=h.front();h.pop();is[f]=false;
        for(struct EDGE* u=p[f];u;u=u->next){
            int v=u->to,w=dis[f]+u->w;
            if(w<dis[v]){
                dis[v]=w;
                if(!is[v]) {h.push(v);is[v]=true;}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX