德克萨斯的夏天炎热,农夫John要将牛奶从威斯康星送到德克萨斯州,帮助人们度过炎热的夏季。地图上有T个城镇,每个城镇都有双向道路连接,每条道路有不同的费用。你需要找到从起始城镇Ts到终点城镇Te的最小总费用。

输入格式:

  • 第一行包含4个整数,空格隔开:T, C, Ts, Te。
  • 接下来的C行,每行包含3个整数,空格隔开:Rs, Re, Ci,描述一条道路的起点、终点和费用。

输出格式:

  • 一个整数,表示从Ts到Te的最小总费用。

数据范围:

  • 1≤T≤2500
  • 1≤C≤6200
  • 1≤Ts, Te, Rs, Re≤T
  • 1≤Ci≤1000

输入样例:

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

题目分析

朴素 Dijikstra; SPFA

代码实现

朴素 Dijikstra

#include <iostream>
#include <cstring>
using namespace std;
const int N = 3000;

int n, m, s, e, g[N][N], dist[N], st[N];
int dijikstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    for (int i = 1; i < n; ++i) {
        int t = -1;
        for (int j = 1; j <= n; ++j)
            if (!st[j] && (dist[j] < dist[t] || t == -1))
                t = j;
        st[t] = 1;
        for (int j = 1; j <= n; ++j)
            if (!st[j]) dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    return dist[e];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s >> e;
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; ++i) g[i][i] = 0;
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    cout << dijikstra();
    return 0;
} 

SPFA

#include <iostream>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
const int M = 1e4;

bitset <M> st;
queue <int> que;
int n, m, s, en, idx, h[M], e[M], w[M], ne[M], dist[M];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa() {
    memset(dist, 0x3f, sizeof dist);
    que.push(s);
    dist[s] = 0;
    st[s] = 1;
    while(que.size()) {
        int t = que.front(); que.pop();
        st[t] = 0;
        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]) {
                    que.push(j);
                    st[j] = 1;
                }
            }
        }
    }
    return dist[en];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m >> s >> en;
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a,b,c), add(b, a, c);
    }
    cout << spfa();
    return 0;
}
分类: DijkstraSPFA

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status