10436 Cheapest way

題目連結

題目翻譯

孟加拉一間運輸公司「Moutushi Enterprise」想重新規劃公車路線，並向乘客收取合理車資。公車每行駛 1 公里要耗費 2 taka（孟加拉貨幣）的油錢，每經過一個車站也要支付該站的過路費；公司會在總成本上加收 10% 的利潤，再把總金額除以該班公車的座位數，即為每位乘客需負擔的車資。給定城市地圖（車站名稱與過路費、站與站之間的道路與距離），請對每筆查詢找出成本最低的路徑，並計算每位乘客需要負擔的車資。

輸入

第一行是地圖（測資）數量。每個地圖分三部分：第一部分第一行是車站數 nStation（0 < nStation < 20），接下來 nStation 行是「車站名稱 過路費」；第二部分第一行是道路數 nPath（0 < nPath < 20），接下來 nPath 行是「station1 station2 distance」（雙向道路，距離單位為公里）；第三部分第一行是查詢數 nQuery（0 < nQuery < 10），接下來 nQuery 行是「station1 station2 passenger」。保證每筆查詢都存在唯一合法的最佳路徑。

輸出

每個地圖先輸出 Map #X（X 為地圖編號，從 1 開始），底下每筆查詢輸出 Query #Y、最佳路徑依序經過的站名（以空白分隔），以及 Each passenger has to pay : 金額 taka（金額四捨五入到小數點後兩位）。

解題思路

把邊權設計成「2 × 道路距離（油錢）+ 到達下一站要付的過路費」，再對每個會被查詢到的起點各自做一次 Dijkstra（起點的初始距離設為該站自己的過路費），這樣求出的最短距離就剛好是「從起點出發、沿途累積的總成本」。為了避免同一個起點重複計算，用 map 快取每個起點算過的最短距離與 prev 陣列；查詢時依 prev 陣列從終點往回推出完整路徑並反轉輸出，車資則是 1.1 × 總成本 ÷ 座位數。另外用一個 map 把車站名稱轉成整數編號，方便用陣列與 Dijkstra 處理。

程式碼

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

#define pb push_back
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>

map<string, int> mp;
vector<string> name;
int id;

int gid(string s) {
    if (mp.count(s)) return mp[s];
    name.pb(s);
    return mp[s] = id++;
}

signed main() { WA();
    int t = 1, T; for (cin >> T; t <= T; t++) { cout << (t-1 ? "\n" : "") << "Map #" << t << '\n';
        mp.clear(); id = 0; name.clear();
        int n; cin >> n;
        vector<vector<PII>> v(n);
        vector<int> p(n);
        for (auto &i : p) {
            string s; int k; cin >> s >> k;
            p[gid(s)] = k;
        }
        int m; for (cin >> m; m--;) {
            string a, b; int k; cin >> a >> b >> k;
            int na = gid(a), nb = gid(b);
            v[na].pb({nb, k});
            v[nb].pb({na, k});
        }
        map<int, vector<int>> mp, path;
        int q = 1, qq; for (cin >> qq; q <= qq; q++) { cout << "Query #" << q << '\n';
            string a, b; int k; cin >> a >> b >> k;
            int na = gid(a), nb = gid(b);
            if (!mp.count(na)) {
                vector<int> &dis = mp[na], &prev = path[na]; dis.assign(n, INF); prev.assign(n, -1);
                priority_queue<PII, vector<PII>, greater<PII>> pq;
                pq.push({p[na], na}); dis[na] = p[na];
                while (pq.size()) {
                    int nd, n; tie(nd, n) = pq.top(); pq.pop();
                    if (nd > dis[n]) continue;
                    for (auto &i : v[n]) {
                        int tod, to; tie(to, tod) = i;
                        if (dis[n] + 2*tod + p[to] < dis[to]) {
                            pq.push({dis[to] = dis[n]+2*tod+p[to], to});
                            prev[to] = n;
                        }
                    }
                }
            }

            vector<int> g;
            for (int i = nb; i != na; i = path[na][i]) g.pb(i); g.pb(na);
            reverse(all(g));
            for (auto &i : g) cout << name[i] << " \n"[&i == &g.back()];

            cout << "Each passenger has to pay : " << fixed << setprecision(2) << 1.1*mp[na][nb]/k << " taka\n";
        }
    }
}