题目链接:https://syzoj.com/problem/5
内存限制：128 MiB 时间限制：1000 ms

题目描述

有 n 个 城市，从1到n给他们编号，它们之间由一些单向道路（即一条道路只能从一个方向走向另一个方向，反之不行）相连，每条路还有一个花费c(i)，表示通过第i条边需要花费c(i)的时间。
现在要求从1走到n。问最少需要多少时间。

输入格式

第一行两个整数n和m，表示有多少个城市和多少条道路。
接下来m行，每行两个整数u、v、c，即有一条从u到v需要花费时间c的道路。

输出格式

一行一个整数，即从1到n最少需要多少时间。

输入样例

4 5
1 2 20
1 3 10
3 2 5
2 4 7
3 4 15

输出数据

22

数据范围与提示

70%的数据，1<=n,m<=1000
100%的数据，1<=n,m<=100000

解题思路

最短路模板问题。

#include <queue>
#include <cstring>
#include <iostream>
#define MAXN 100005 
using namespace std;
struct edge {
    int u, v, w;
}e[MAXN];
int cnt, f[MAXN], dis[MAXN], vis[MAXN];
void Add(int u, int v, int w) {
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void Spfa(int s) {
    queue <int> Q;
    Q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    while (!Q.empty()) {
        int t = Q.front();
        Q.pop();
        vis[t] = 0;
        for (int i = f[t]; i; i = e[i].u) {
            int v = e[i].v;
            if (dis[v] > dis[t] + e[i].w) {
                dis[v] = dis[t] + e[i].w;
                if (!vis[v]) {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}
int main() {
    int n, m, s, t, w;
    while (cin >> n >> m) {
        cnt = 0;
        memset(f, 0, sizeof(f));
        memset(vis, 0, sizeof(vis));
        memset(dis, 0x3f, sizeof(dis));
        for (int i = 0; i < m; i++) {
            cin >> s >> t >> w;
            Add(s, t, w);
        }
        Spfa(1);
        cout << dis[n] << endl;
    }
    return 0;
}