62 lines
1009 B
C++
62 lines
1009 B
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
int dis[2501];
|
||
bool exist[2501];//标记每个点是否在queue中
|
||
struct point
|
||
{
|
||
int to;
|
||
int w;
|
||
};
|
||
int n,m,s,t;
|
||
vector<point> graph[2501];
|
||
|
||
void SPFA()
|
||
{
|
||
memset(dis, 0x3f, sizeof(dis));
|
||
dis[s] = 0; // 注意起 始点是s！！！
|
||
queue<int> q;
|
||
q.push(s);
|
||
exist[s]=1;
|
||
|
||
while(q.size()>0)
|
||
{
|
||
int from=q.front();
|
||
q.pop();
|
||
exist[from]=0;
|
||
for(int i=0;i<graph[from].size();i++)
|
||
{
|
||
// for(int temp:graph[from])
|
||
|
||
int to=graph[from][i].to;
|
||
int w=graph[from][i].w;
|
||
if(dis[from]+w<dis[to])
|
||
{
|
||
dis[to]=dis[from]+w;
|
||
if(exist[to]==0)
|
||
{
|
||
q.push(to);
|
||
exist[to]=1;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(0);
|
||
|
||
cin >> n >> m >> s >> t;
|
||
for (int i = 1; i <=m ; i++) {
|
||
int a,b,c;
|
||
cin >> a >> b >> c;
|
||
graph[a].push_back({b,c});
|
||
graph[b].push_back({a,c});
|
||
}
|
||
|
||
SPFA();
|
||
|
||
cout << dis[t] << endl;
|
||
return 0;
|
||
}
|