Sorry 数据小是真的能为所欲为的

Problem

运输货物需要缴纳过路费。进入一个村庄需要缴纳 1 个单位的货物，而进入一个城市每 20 个单位的货物就要上缴 1 个单位。多组询问，对于每组询问，找出一条缴纳过路费最少的路线。无向图中 N 个节点，询问的起点、终点、需要运输的物品数（到达终点时的物品数）不同。
Translated by Awson

虽然可能与原题意有点简略但是也差不多

Solution

什么，反向 Djikstra？
什么，正向 Dijkstra 没法走字典序最小？
NAIVE

二分正向 Dijkstra，再在最短路树上爆搜
10ms 稳

抱歉，数据小是真的能为所欲为的.jpg

至于为什么能最短路呢...
题意满足三角形不等式
边权随到该边的道路变化而变化，因而对求最短路树没有实质性影响
感性理解下（雾）

Code

// Code by ajcxsu
// Problem: toll

#include<bits/stdc++.h>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;
typedef long long ll;

const int N=500, M=1e4+10;
int h[N], to[M], nexp[M], p=1;
int typ[N];
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

ll dist[N], adis[N];
bool S[N];

void dij(int s, int t, ll w) {
    CLR(S), memset(dist, 0x3f, sizeof(dist));
    dist[s]=0;
    int uu=0;
    ll minn, W;
    while(1) {
        minn=0x3f3f3f3f3f3f3f3fll, uu=0;
        for(int i=1;i<N;i++)
            if(!S[i] && dist[i]<minn) minn=dist[i], uu=i;
        if(!uu) break;
        S[uu]=1;
        for(int u=h[uu];u;u=nexp[u]) {
            W=typ[to[u]]?(w-minn-1)/20+1:1;
            if(!S[to[u]] && dist[to[u]]>dist[uu]+W)
                dist[to[u]]=dist[uu]+W;
        }
    }
}

vector<char> ans;
bool rua(int x, int v, ll w) {
    vector<int> t;
    ll W;
    ans.push_back(x);
    if(x==v) return true;
    for(int u=h[x];u;u=nexp[u]) {
        W=typ[to[u]]?(w-adis[x]-1)/20+1:1;
        if(adis[to[u]]==adis[x]+W) t.push_back(to[u]);
    }
    sort(t.begin(), t.end());
    for(int i=0, len=t.size(); i<len; i++)
        if(rua(t[i], v, w)) return true;
    ans.pop_back();
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    for(int i='A'; i<='Z'; i++) typ[i]=1;
    int m, cnt=0;
    while(cin>>m, m!=-1) {
        char u, v;
        CLR(h), p=1;
        for(int i=1;i<=m;i++)
            cin>>u>>v, ins(u, v), ins(v, u);
        int w;
        cin>>w>>u>>v;
        ll l=w, r=1e15, mid;
        while(r>l) {
            mid=(l+r)>>1ll;
            dij(u, v, mid);
            if(mid-dist[v]>=w) r=mid, memcpy(adis, dist, sizeof(dist));
            else l=mid+1;
        }
        cout<<"Case "<<++cnt<<":"<<endl;
        cout<<r<<endl;
        ans.clear();
        rua(u, v, r);
        for(int i=0, len=ans.size(); i<len; i++) {
            if(i) cout<<'-';
            cout<<ans[i];
        }
        cout<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-uva-10537.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆