HDU 2112 HDU Today：map 映射站點名 + Dijkstra 鄰接表優化

題目同 HDU 2112

此處採用 map<string, int> 映射站點名，鄰接表存儲圖，優先隊列優化 Dijkstra。

核心代碼結構

#include <map>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;

struct Edge { int to, w; };
const int MAXV = 155, INF = 1e9;

map mp;
vector G[MAXV];
int dist[MAXV];

int get_id(const string& s) {
    if (!mp.count(s)) mp[s] = mp.size() + 1;
    return mp[s];
}

void dijkstra(int src, int V) {
    fill(dist+1, dist+V+1, INF);
    priority_queue, vector>, greater>> pq;
    dist[src] = 0; pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto &e : G[u]) {
            if (dist[e.to] > d + e.w) {
                dist[e.to] = d + e.w;
                pq.push({dist[e.to], e.to});
            }
        }
    }
}

int main() {
    int N;
    while (scanf("%d", &N), N != -1) {
        mp.clear(); for (int i=0; i