最短路模板(SPFA POJ2387)

时间:2024-05-30 17:07:44

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
const int maxn=2021;
int n,m,inq[maxn],dis[maxn];
vector<pair<int,int> >v[maxn];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
int a,b,w;
cin>>a>>b>>w;
v[a].pb(mp(b,w));
v[b].pb(mp(a,w));
}
queue<int>p;
p.push(1);
inq[1]=1;
for(int i=1;i<=max(n,m);i++)dis[i]=INF;
dis[1]=0;
while(!p.empty()){
int now=p.front();
p.pop();
inq[now]=0;
for(int i=0;i<v[now].size();i++){
int ne=v[now][i].fi;
if(dis[now]+v[now][i].se<dis[ne]){
dis[ne]=dis[now]+v[now][i].se;
if(!inq[ne]){
inq[ne]=1;
p.push(ne);
}
}
}
}
cout<<dis[m];
return 0;
}