ProgramAlgTrain/20240919/CSP常考算法模板/最短路径/单源最短路径Dijkstra.cpp

#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;
}