66 lines
1.2 KiB
C++
66 lines
1.2 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
const int N = 2501;
|
||
const int M = 15001;
|
||
|
||
struct point {
|
||
int id;
|
||
int len;
|
||
};
|
||
|
||
vector<point> g[N];
|
||
int t, c, ts, te;
|
||
int rs, re, ci;
|
||
int dis[N];
|
||
bool vis[N];
|
||
|
||
struct cmp //仿函数
|
||
{
|
||
bool operator()(point a, point b) {
|
||
return a.len > b.len; //priority_queue的排序规则与sort的规则相反
|
||
}
|
||
};
|
||
|
||
priority_queue<point, vector<point>, cmp> pq;
|
||
|
||
void Dijkstra()
|
||
{
|
||
memset(dis, 0x3f, sizeof(dis));
|
||
dis[ts] = 0; // 注意起 始点是ts！！！
|
||
pq.push({ts, 0});
|
||
|
||
while (pq.size()>0) {
|
||
int id = pq.top().id; // 取出当前距离源点最近的点
|
||
pq.pop();
|
||
|
||
if (vis[id]) continue;
|
||
vis[id] = 1;
|
||
|
||
for (point e:g[id]) {
|
||
|
||
if (dis[e.id] > dis[id] + e.len) {
|
||
dis[e.id] = dis[id] + e.len;
|
||
pq.push({e.id, dis[e.id]});
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(0);
|
||
|
||
cin >> t >> c >> ts >> te;
|
||
for (int i = 0; i < c; i++) {
|
||
cin >> rs >> re >> ci;
|
||
g[rs].push_back({re,ci});
|
||
g[re].push_back({rs,ci});
|
||
}
|
||
|
||
Dijkstra();
|
||
|
||
cout << dis[te] << endl;
|
||
return 0;
|
||
}
|