传送门:https://ac.nowcoder.com/acm/problem/52805
我佛了,还能跑边图啊!!!
跑边图不能用vector啦啦啦啦啦
具体也不难,就直接上代码了
#include<cstdio> #include<queue> #include<iostream> #include<cstring> #include<vector> using namespace std; typedef long long ll; const int maxn = 2e5 + 7; const int INF = 0x3f3f3f3f; int n, m; int head[maxn]; struct edge { int p; ll len; edge(int _p, ll _len) :p(_p), len(_len) {} }; struct Node { int p; ll len; ll c; int next; }G[maxn]; int cnt = 1; void add(int be, int en, ll c,ll len) { G[cnt].p = en; G[cnt].next = head[be]; head[be] = cnt; G[cnt].len = len; G[cnt].c = c;//头插法 cnt++; } bool operator <(const edge a, const edge b) { return a.len > b.len; } ll dis[maxn]; int vis[maxn]; ll dij() { for (int i = 0; i < maxn; i++) dis[i] = 1e17; priority_queue<edge>que; for (int i = head[1]; i; i = G[i].next) { dis[i] = G[i].len; que.push(edge(i, dis[i])); } ll a = 1e16; while (que.size()) { edge ans = que.top(); que.pop(); if (vis[ans.p]) continue; vis[ans.p] = 1; int x = G[ans.p].p; if (n == x) a = min(dis[ans.p], a); for (int i = head[x]; i; i = G[i].next) { if (dis[i] > dis[ans.p] + G[i].len + abs(G[ans.p].c - G[i].c)) { dis[i] = dis[ans.p] + G[i].len + abs(G[ans.p].c - G[i].c); que.push(edge(i, dis[i])); } } } return a; } int main() { int be, en; ll c, len; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d %d %lld %lld", &be, &en, &c, &len); add(be, en, c, len); add(en, be, c, len); } ll ans = dij(); cout << ans << endl; return 0; }