【LOJ119】单源最短路 模板

problem

• 给你一个n个点m条边的无向图，求 s 到 t 的最短路。

solution

• SPFA模板

codes

#include<iostream>
#include<queue>
#include<cstring>
#define maxn 2500+10
#define maxm 6200+10
using namespace std;
const int inf = 2147483647;

//Grape
int n, m, s, t;
struct Edge{int v, w, next;}e[maxm<<2];
int tot, head[maxn];
void AddEdge(int u, int v, int w){
    tot++; e[tot].v=v; e[tot].w=w; e[tot].next=head[u]; head[u]=tot;
}

//SPFA
int dist[maxn], book[maxn];
queue<int>q;
void spfa(){
    for(int i = 1; i <= n; i++)dist[i]=inf;
    dist[s]=0; book[s]=1; q.push(s);
    while(q.size()){
        int u = q.front();  q.pop(); book[u]=0;
        for(int i = head[u]; i != -1; i = e[i].next){
            int v = e[i].v, w = e[i].w;
            if(dist[v]>dist[u]+w){
                dist[v] = dist[u]+w;
                if(!book[v]){
                    book[v] = 1;  q.push(v);
                }
            }
        }
    }
}

int main(){
    memset(head,-1,sizeof(head));
    cin>>n>>m>>s>>t;
    for(int i = 1; i <= m; i++){
        int x, y, z; cin>>x>>y>>z;
        AddEdge(x,y,z); AddEdge(y,x,z);
    }
    spfa();
    cout<<dist[t];
    return 0;
}