题目链接:https://www.acwing.com/problem/content/description/851/
时/空限制：1s / 64MB

题目描述

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

输出格式

输出一个整数，表示1号点到n号点的最短距离。

如果路径不存在，则输出-1。

数据范围

1≤n≤500,
1≤m≤10^5,
图中涉及边长均不超过10000。

输入样例

3 3
1 2 2
2 3 1
1 3 4

输出样例

3

解题思路

题意:求1~n的最短距离。
思路:利用Dijkstra算法，因为边太多，注意要用邻接矩阵保存路径。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MAXM = MAXN << 1;
const int inf = 0x3f3f3f3f;
bool vis[MAXN];
int dis[MAXN], mp[MAXN][MAXN];
int Dijkstra(int s, int n) {
    for (int i = 1; i <= n; i++) {
        dis[i] = inf;
        vis[i] = false;
    }
    dis[s] = 0;
    for (int i = 0; i < n - 1; i++) {
        int k = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (!~k || dis[j] < dis[k]))
                k = j;
        vis[k] = true;
        for (int j = 1; j <= n; j++)
            dis[j] = min(dis[j], dis[k] + mp[k][j]);
    }
    if (dis[n] < inf)
        return dis[n];
    return -1;
}
int main() {
    int n, m;    
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                mp[i][j] = inf;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        mp[u][v] = min(mp[u][v], w);
    }
    printf("%d\n", Dijkstra(1, n));
    return 0;
}