SPFA.cpp

#include <iostream>
#include <queue>
using namespace std;
int n,m,a,b,k;
int dist[150000];
bool inq[150000];
struct Edge{
	int u,v,c,next;
}edge[150000];
int e=0,head[150000];
void addnote(int u,int v,int c){
	e++;
	edge[e].u=u;
	edge[e].v=v;
	edge[e].c=c;
	edge[e].next=head[u];
	head[u]=e;
}
queue<int> q;
void spfa(int s){
	for(int i=1;i<=n;i++) dist[i]=99999999;
	dist[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=head[u];i!=0;i=edge[i].next){
			int v=edge[i].v;
			if(dist[v]>dist[u]+edge[i].c)
			{
				dist[v]=dist[u]+edge[i].c;
				if(!inq[v]){
					q.push(v);
					inq[v]=1;
				}
			}
		}
	}
}
 
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int t,g,b;
		cin>>t>>g>>b;
		addnote(t,g,b);
	}
	cin>>a>>b>>k; 
	spfa(a);
	cout<<dist[b];
	return 0;
}