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

题目描述

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

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

数据保证不存在负权回路。

输入格式

第一行包含整数n和m。

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

输出格式

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

如果路径不存在，则输出”impossible”。

数据范围

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

输入样例

3 3
1 2 5
2 3 -3
1 3 4

输出样例

2

解题思路

题意:求1~n的最短距离。
思路:题目都说了让我们用Spfa。。。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int inf = 0x3f3f3f3f;
bool vis[MAXN];
int f[MAXN], dis[MAXN], Adj;
struct AddTab {
    int u, v, w;
    AddTab() {}
    AddTab(int u, int v, int w) : u(u), v(v), w(w) {}
}e[MAXM];
void Add_Adj(int u, int v, int w) {
    e[++Adj] = AddTab(f[u], v, w);
    f[u] = Adj;
}
void init() {
    Adj = 0;
    memset(f, -1, sizeof(f));
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
}
int Spfa(int s, int n) {
    queue <int> Q;
    Q.push(s);
    dis[s] = 0;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for (int i = f[u]; ~i; i = e[i].u) {
            int v = e[i].v;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    if (dis[n] < inf)
        return dis[n];
    return -1;
}
int main() {
    int n, m, k;
    init();
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        Add_Adj(u, v, w);
    }
    int cnt = Spfa(1, n);
    if (~cnt)
        printf("%d\n", cnt);
    else printf("impossible\n");
    return 0;
}