AcWing - Dijkstra求最短路 II(堆优化Dijkstra&邻接表)

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

题目描述

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

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

输入格式

第一行包含整数n和m。

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

输出格式

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

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

数据范围

1≤n,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 = 1e5 + 5;
const int MAXM = MAXN << 1;
const int inf = 0x3f3f3f3f;
typedef pair <int, int> PII;
bool vis[MAXN];
int f[MAXN], dis[MAXN], Adj = 0;
struct AdjTab {
    int u, v, w;
    AdjTab() {}
    AdjTab(int u, int v, int w) : u(u), v(v), w(w) {}
}e[MAXN];
void Add_Adj(int u, int v, int w) {
    e[++Adj] = AdjTab(f[u], v, w);
    f[u] = Adj;
}
int Dijkstra(int s, int n) {
    for (int i = 1; i <= n; i++) {
        dis[i] = inf;
        vis[i] = false;
    }
    dis[s] = 0;
    priority_queue <PII, vector <PII>, greater<PII> > Q;
    Q.push(PII(dis[s], s));
    while (!Q.empty()) {
        PII p = Q.top();
        Q.pop();
        if (vis[p.second])
            continue;
        vis[p.second] = true;
        for (int j = f[p.second]; ~j; j = e[j].u) {
            if (dis[e[j].v] > p.first + e[j].w) {
                dis[e[j].v] = p.first + e[j].w;
                Q.push(PII(dis[e[j].v], e[j].v));
            }
        }
    }
    if (dis[n] < inf)
        return dis[n];
    return -1;
}
int main() {
    int n, m;    
    scanf("%d%d", &n, &m);
    memset(f, -1, sizeof(f));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        Add_Adj(u, v, w);
    }
    printf("%d\n", Dijkstra(1, n));
    return 0;
}