CODE THANKS FESTIVAL 2015 G: カメレオン
解法
ダイクストラやるだけ。
コード
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <tuple> #include <sstream> #include <typeinfo> #include <fstream> #include <random> #include <queue> #include <deque> #include <iterator> #include <map> using namespace std; typedef long long ll; const ll INF = 10000000000000000; struct Edge { int to, color; ll weight; bool operator<(const Edge& a) const { return weight > a.weight; } Edge() {} Edge(int b, int c, ll t) { to = b, color = c, weight = t; } }; int main() { int N, M; scanf("%d %d", &N, &M); vector<vector<Edge>> graph(N); vector<map<int, ll>> dist(N); vector<map<int, bool>> used(N); for (int i = 0; i < M; ++i) { int a, b, c, t; scanf("%d %d %d %d", &a, &b, &c, &t); a--; b--; Edge e1(b, c, t); Edge e2(a, c, t); dist[a][c] = INF; dist[b][c] = INF; used[a][c] = false; used[b][c] = false; graph[a].push_back(e1); graph[b].push_back(e2); } priority_queue<Edge> que; que.push(Edge(0, 1, 0)); dist[0][1] = 0; ll ans = INF; while (!que.empty()) { int v = que.top().to; int color = que.top().color; ll w = que.top().weight; if (v == N - 1) { ans = w; break; } que.pop(); if (used[v][color]) continue; used[v][color] = true; for (Edge e : graph[v]) { if (dist[e.to][e.color] > w + e.weight + abs(color - e.color)) { dist[e.to][e.color] = w + e.weight + abs(color - e.color); que.push(Edge(e.to, e.color, dist[e.to][e.color])); } } } printf("%lld\n", ans); }