热浪

单源最短路 T2 热浪 - 计蒜客 T1658 - Virtual Judge (csgrandeur.cn) 德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John 此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

FJ 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过 $T(1\le T\le 2,500)$ 个城镇，方便地标号為 $1$ 到 $T$。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含 $C(1\le C\le 6,200)$ 条直接连接 $2$ 个城镇的道路。每条道路由道路的起点 $R_s$，终点 R_e$$(1 \le R_s,R_e \le T)，和花费$C_i(1\le C_i\le 1,000)$ 组成。求从起始的城镇 $T_s(1\le T_s\le T)$ 到终点的城镇 $T_e(1\le T_e\le T)$ 最小的总费用。

输入格式

第 $1$ 行：$4$ 个由空格隔开的整数：$T,C,T_s,T_e$。

第 $2$ 到第 $C+1$ 行：第 $i+1$ 行描述第 $i$ 条道路。有 $3$ 个由空格隔开的整数：$R_s,R_e,C_i$。

输出格式

一个单独的整数表示从 $T_s$​ 到 $T_e$​ 的最小总费用。数据保证至少存在一条道路。

输入

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

输出

7

思路

简单的dijkstra模板题 朴素版dijkstra时间复杂度为 $O(N^2)$, 堆优化版本为 $O(M\log N)$ spfa则为$O(M)$ 这里三种算法都可以用

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 3e3, M = 2 * 6200 + 10;
int h[N], e[M], w[M], ne[M], idx;
int n, m;
int start, ed;
int dist[N];
bool st[N];
 
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
 
void spfa(int start)
{
    int q[N] = {0}, hh = 0, tt = 1;
    q[0] = start;
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    dist[start] = 0;
    st[start] = true;
    while (hh != tt)
    {
        int t = q[hh++];
        if (hh == N)
            hh = 0;
        st[t] = false;
 
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[++tt] = j;
                    if (tt == N)
                        tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}
 
void dijkstra(int start)
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(dist, 0x3f, sizeof dist);
    q.push({0, start});
    dist[start] = 0;
 
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int ver = t.y;
        if (st[ver])
            continue;
        st[ver] = true;
 
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > t.x + w[i])
            {
                // cout << dist[j] << endl;
                dist[j] = t.x + w[i];
                q.push({dist[j], j});
            }
        }
    }
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> start >> ed;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dijkstra(start);
    cout << dist[ed] << endl;
    return 0;
}