1818. 最短路径2

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 110, inf = 999999999;

typedef struct edge {                             /* 边的结构体 */
    edge (int x, int y = inf) {                   /* 构造函数 */
        next = x;
        len = y;
    }
    int next, len = inf;
} edge;

vector<edge> g[MAX];
int dist[MAX];
int num[MAX];
bool visited[MAX];
int n, m;

int findm() {                          
    int min = -1, mindist = inf;
    for (int i = 1; i <= n; i++) {
        if (!visited[i] && dist[i] < mindist) {
            min = i;
            mindist = dist[i];
        }
    }
    return min;
}

void dijkstra() {
    dist[1] = 0;
    num[1] = 1;
    while (true) {
        int v = findm();
        if (v == -1) break;
        visited[v] = true;
        for (int i = 0; i < g[v].size(); i++) {
            int w = g[v][i].next;
            if (!visited[w]) {
                if (dist[w] > dist[v] + g[v][i].len) {
                    dist[w] = dist[v] + g[v][i].len;
                    num[w] = num[v];
                } else if (dist[w] == dist[v] +g[v][i].len) num[w] += num[v];
            }
        }
    }
}

int main() {
    fill(dist, dist + MAX, inf);
    cin >> n >> m;
    while (m--) {
        int v, w, d;
        scanf("%d %d %d", &v, &w, &d);
        edge t(w, d);                             /* 构造邻边 */
        g[v].push_back(t);                        /* 将边push入结点V的邻接表 */
    }
    dijkstra();
    if (dist[n] != inf) printf("%d %d\n", dist[n], num[n]);
    else printf("-1 0\n");
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

struct Node {
    Node(int id, int dist) : id(id), dist(dist) {}

    bool operator<(const Node& node) const {
        return dist > node.dist;
    }

    int id, dist;
};

int main() {
    constexpr int inf = 100010;
    int n, m;
    cin >> n >> m;

    vector<vector<int>> map(n + 1, vector<int>(n + 1, inf)), cnt(n + 1, vector<int>(n + 1));

    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        map[u][v] = w, ++cnt[u][v];
    }

    for (int i = 1; i <= n; ++i) {
        map[i][i] = 0;
    }

    vector<int> d(n + 1, inf), visited(n + 1), c(n + 1);
    d[1] = 0, c[1] = 1;

    priority_queue<Node> queue;
    queue.push({ 1,0 });

    while (!queue.empty()) {
        auto node = queue.top();
        queue.pop();

        visited[node.id] = 1;

        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                if (node.dist + map[node.id][i] < d[i]) {
                    d[i] = node.dist + map[node.id][i], c[i] = c[node.id] * cnt[node.id][i];
                    queue.push({ i,d[i] });
                }
                else if (node.dist + map[node.id][i] == d[i]) {
                    c[i] += c[node.id] * cnt[node.id][i];
                }
            }
        }
    }

    int res = d.back() == inf ? -1 : d.back();
    printf("%d %d\n", res, c.back());
}

#include <bits/stdc++.h>

#define ll   long long
#define SIZE 1000001

using namespace std;

int n, m, u, v, w;
bool visited[SIZE] = {false};
int D[SIZE] = {INT_MAX};
bool S[SIZE] = {false};
int NUM[SIZE] = {0};
map<int, map<int, int>> G;
map<int, map<int, int>> T;

int get_min_index() {
    int min = INT_MAX;
    int min_index = -1;
    for (int i = 1; i <= n; ++i) {
        if (!S[i] && D[i] < min) {
            min = D[i];
            min_index = i;
        }
    }
    return min_index;
}

void dijkstra() {
    D[1] = 0;
    NUM[1] = 1;
    for (int i = 2; i <= n; ++i) {
        D[i] = INT_MAX;
    }

    for (;;) {
        int min_index = get_min_index();
        if (min_index < 0) {
            break;
        }
        int min = D[min_index];
        S[min_index] = true;
        for (int i = 1; i <= n; ++i) {
            if (!S[i] && G[min_index].count(i) && D[i] > min + G[min_index][i]) {
                D[i] = min + G[min_index][i];
                NUM[i] = NUM[min_index] * T[min_index][i];
            } else if (!S[i] && G[min_index].count(i) && D[i] == min + G[min_index][i]) {
                NUM[i] += NUM[min_index] * T[min_index][i];
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w;
        if (G[u].count(v)) {
            T[u][v] += 1;
        } else {
            G[u][v] = w;
            T[u][v] = 1;
        }
    }
    dijkstra();
    cout << (D[n] == INT_MAX ? -1 : D[n]) << " " << NUM[n] << endl;
    return 0;
}