计蒜客-骑车比赛

2019-08-04

蒜头君准备去参加骑车比赛，比赛在 n 个城市间进行，编号从 1 到 n。选手们都从城市 1 出发，终点在城市 n。

已知城市间有 m 条道路，每条道路连接两个城市，注意道路是双向的。现在蒜头君知道了他经过每条道路需要花费的时间，他想请你帮他计算一下，他这次比赛最少需要花多少时间完成。

输入格式

第一行输入两个整数 n, m（1≤n≤1,000,1≤m≤5,000），分别代表城市个数和道路总数。接下来输入 m 行，每行输入三个数字 a, b, c（1≤a,b≤n,1≤c≤200），分别代表道路的起点和道路的终点，以及蒜头君骑车通过这条道路需要花费的时间。保证输入的图是连通的。

输出格式

输出一行，输出一个整数，输出蒜头君完成比赛需要的最少时间。

样例输入

样例输出

dijstra

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

const int N = 1005;
const int M = 5005;

struct edge {
    int v, w, next;
    edge() {}
    edge(int _v, int _w, int _next):v(_v), w(_w), next(_next) {}
} E[2 * M];

int head[N];
int cnt;

void init() {
    memset(head, -1, sizeof head);
    cnt = 0;
}

void insert(int u, int v, int w) {
    E[cnt] = edge(v, w, head[u]);
    head[u] = cnt++;
}


void insert2(int u, int v, int w) {
    insert(u, v, w);
    insert(v, u, w);
}

int dis[N];
bool vis[N];
int n, m;
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap; //利用set 的特性来模拟最小堆

bool dijstra(int u) {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    dis[u] = 0;
    min_heap.insert(make_pair(0, u)); //初始化小跟堆

    for (int i = 0; i < n; i++) {
        if (min_heap.size() == 0) { // 如果小根堆中没有可用顶点，说明有顶点无法从源点到达，算法结束
            return false;
        }
		
        // 获取堆顶元素，并将堆顶元素从堆中删除
        set<PII, less<PII> >::iterator it = min_heap.begin();
        int min_v = it->second;
        vis[min_v] = true;
        min_heap.erase(*it);

        for (int e = head[min_v]; e != -1; e = E[e].next) { // 进行和普通 dijkstra 算法类似的松弛操作
            int v = E[e].v;
            int w = E[e].w;
            if (!vis[v] && dis[min_v] + w < dis[v]) {
                // 先将对应的 pair 从堆中删除，再将更新后的 pair 插入堆
                min_heap.erase(make_pair(dis[v], v));
                dis[v] = dis[min_v] + w;
                min_heap.insert(make_pair(dis[v], v));
            }
        }
    }
    return true;
}

int main() {
    int a, b, c;
    cin >> n >> m;
    init();
    while (m--) {
        cin >> a >> b >> c;
        insert2(a, b, c);
    }
    dijstra(1);
    cout << dis[n] << endl;
}

SPFA

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1001;
const int M = 5001;

struct edge {
    int v, w, next;
    edge(int _v, int _w, int _next): v(_v), w(_w), next(_next){}
    edge() {}
} E[2 * M];

int p[N];
int cnt = 0;

void init() {
    memset(p, -1, sizeof p);
    cnt = 0;
}

void insert(int u, int v, int w) {
    E[cnt] = edge(v, w, p[u]);
    p[u] = cnt++;
}

void insert2(int u, int v, int w) {
    insert(u, v, w);
    insert(v, u, w);
}

int dis[N];
bool vis[N];
queue<int> q;

void spfa(int s) {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    dis[s] = 0;
    vis[s] = true;
    q.push(s);

    while (!q.empty()) {
        int tmp = q.front();
        q.pop();
        vis[tmp] = false;
        for (int e = p[tmp]; e != -1; e = E[e].next) {
            int v = E[e].v;
            int w = E[e].w;
            if (dis[tmp] + w < dis[v]) {
                dis[v] = dis[tmp] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    init();
    int a, b, c;
    while (m--) {
        cin >> a >> b >> c;
        insert2(a, b, c);
    }
    spfa(1);
    cout << dis[n] << endl;
    return 0;
}