L3-1 直捣黄龙 (30 分)

题目描述：

n个点，m条边，起点是s，终点是t，你需要从s杀到t点，除了s点外每个点都有一个数量，代表这个点上有的敌军的数量

m条边，每条边u v c表示一条权值为c的双向边，连接着u和v

你需要求一条最短路的距离，以及最短路的数量，同时因为可能存在多条最短路，我们要在路程最短的基础上选择经过点的数量最多的方案，如果还有多条路径，我们就选择杀敌数量最多的路径，保证只存在一条这样的路径，输出这条路径，以及最短路的数量、最短路的距离、杀敌数量

思路：

迪杰斯塔拉模拟就行，需要维护的变量有点多，仔细点写就行

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int a, b, c;
string s, t;
int qi, zh;
int id;
map<string, int>mp;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}
int val[MAX];
int dis[MAX];
int cit[MAX];
int arm[MAX];
string fuck[MAX];
bool vis[MAX];
int lu[MAX];
int fa[MAX];
void dijkstar(int s, int t){
    priority_queue<pii, vector<pii>, greater<pii> >q;
    mem(dis, inf);
    dis[s] = 0;
    for(int i = 1; i <= id; ++i)lu[i] = 1;
    q.push(m_p(0, s));
    while (!q.empty()) {
        auto [d, u] = q.top();q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                lu[v] = lu[u];
                dis[v] = dis[u] + tr[i].val;
                cit[v] = cit[u] + 1;
                arm[v] = arm[u] + val[v];
                fa[v] = u;
                q.push(m_p(dis[v], v));
            }
            else if(dis[v] == dis[u] + tr[i].val){
                lu[v] += lu[u];
                if(cit[v] < cit[u] + 1){
                    cit[v] = cit[u] + 1;
                    arm[v] = arm[u] + val[v];
                    fa[v] = u;
                }
                else if(cit[v] == cit[u] + 1){
                    if(arm[v] < arm[u] + val[v]){
                        arm[v] = arm[u] + val[v];
                        fa[v] = u;
                    }
                }
            }
        }
    }
    x = t;
    vector<int>v;
    while (x != s) {
        v.push_back(x);
        x = fa[x];
    }
    reverse(v.begin(), v.end());
    cout << fuck[1];
    for(auto x : v){
        cout << "->"<< fuck[x];
    }
    cout << endl;
    cout << lu[t] << ' ' << dis[t] << ' ' << arm[t];
}

void work(){
    cin >> n >> m >> s >> t;
    fuck[1] = s;fuck[2] = t;
    mp[s] = ++id;mp[t] = ++id;
    for(int i = 2; i <= n; ++i){
        cin >> s >> x;
        if(mp.count(s))val[mp[s]] = x;
        else {
            mp[s] = ++id;
            fuck[id] = s;
            val[id] = x;
        }
    }
    for(int i = 1; i <= m; ++i){
        cin >> s >> t >> c;
        a = mp[s];b = mp[t];
        add(a, b, c);
        add(b, a, c);
    }
    dijkstar(1, 2);
}


int main(){
    io;
    work();
    return 0;
}