GPLT L3-011. 直捣黄龙 dijkstra

题目链接戳这里
和紧急救援差不多.用的dijkstra
用的是map来映射值与名,名与值
傻了一个小地方: 遇到同样长度的路径时,要考量其它数据再决定是否要改变路径,比如这条路虽长度一样,但其它参数更优.但是对于到某个点的路径数,但凡遇到有同样长度的就可以累加了,不必再考量..
一样状态数有点多,但是只是繁琐而已.

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

#define mst(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define fi first
#define se second
const int inf = 0x3f3f3f3f, maxN = 205;
int N, M;
map<int, string> mp;
map<string, int> rmp;
// 图 访问标记 最短距离 路径记录
int G[maxN][maxN], vis[maxN], d[maxN], way[maxN];
// 城内敌数 灭敌数 城镇数 路径条数
int ds[maxN], mds[maxN], czs[maxN], ts[maxN];

void dijkstra(int s) {
    mst(vis, 0);
    mst(d, inf);
    mst(way, -1);
    mst(mds, 0);
    mst(czs, 0);
    mst(ts, 0);
    d[s] = 0;
    ts[s] = 1;

    while (1) {
        int u = -1;
        rep(i, 0, N) if (!vis[i] && (u == -1 || d[i] < d[u])) u = i;
        if (u == -1)
            break;

        vis[u] = 1;
        rep(i, 0, N) {
            if (!vis[i] && G[u][i] != inf) {
                // 距离更短
                if (d[u] + G[u][i] < d[i]) {
                    d[i] = d[u] + G[u][i];
                    way[i] = u;
                    mds[i] = mds[u] + ds[i];
                    czs[i] = czs[u] + 1;
                    ts[i] = ts[u];
                } else if (d[u] + G[u][i] == d[i]) {
                    ts[i] += ts[u];
                    if (czs[u] + 1 > czs[i]) {
                        way[i] = u;
                        mds[i] = mds[u] + ds[i];
                        czs[i] = czs[u] + 1;
                    } else if (czs[u] + 1 == czs[i]) {
                        if (mds[u] + ds[i] > mds[i]) {
                            way[i] = u;
                            mds[i] = mds[u] + ds[i];
                        }
                    }
                }
            }
        }
    }
}

void print_path(int e) {
    int rway[maxN], cnt = 0;
    int te = e;
    while (te != -1) {
        rway[cnt++] = te;
        te = way[te];
    }
    rep(i, 0, cnt) {
        if (i)
            cout << "->";
        cout << mp[rway[cnt - 1 - i]];
    }
    cout << endl << ts[e] << " " << d[e] << " " << mds[e];
}
int main() {
    // freopen("data.in", "r", stdin);
    string a, b;
    cin >> N >> M >> a >> b;
    int c;
    int s = 0, e;
    mp[s] = a;
    rmp[a] = 0;
    ds[s] = 0;
    rep(i, 1, N) {
        cin >> a >> ds[i];
        mp[i] = a;
        rmp[a] = i;
        if (a == b)
            e = i;
    }
    mst(G, inf);
    rep(i, 0, M) {
        cin >> a >> b >> c;
        int na = rmp[a], nb = rmp[b];
        G[na][nb] = G[nb][na] = c;
    }
    dijkstra(s);
    print_path(e);
    return 0;
}