題干：

鏈接：https://ac.nowcoder.com/acm/contest/1080/D
來源：牛客網
?

這天，tokitsukaze帶著她的艦隊去才歸一兒海探索。這個海域有n個站點，深海艦隊控制著這片海域的m條航線，這些航線連接著這n個點，第i條航線連接著ui，vi兩個點。航線都是正確的，也就是說沒有重復的航線，也沒有任何一個點與自己相連。tokitsukaze的艦隊經過第i條航線時，會受到來自深海艦隊的ai點傷害。

tokitsukaze可以在某個休息站點將接下來的戰斗切換至夜戰模式，這樣在她的艦隊經過第i條航線時，受到的傷害就變為bi，不過一旦切換到夜戰模式就不能再次切換回來，所以她必須考慮清楚在哪里切換。

現在有個限時活動。活動難度分為1,2,3,4,...n，在難度1下，tokitsukaze可以在任意站點切換到夜戰模式，而在難度2下，不能在站點1切換到夜戰模式，在難度3下，不能在站點1,2切換模式...以此類推，即在難度k下，tokitsukaze不能在站點1,2,3,4,5...k-1切換模式。同時，活動還要求在游戲結束時必須處于夜戰模式。

現在tokitsukaze的艦隊從s點出發，要前往深海大本營所在的t點。請你告訴她，在難度為1,2,3,4,5...n時，她的艦隊結束游戲時受到的最小傷害。

輸入描述:

第一行包括2個正整數n，m，(2≤n≤10^5，1≤m≤min(n*(n-1)/2,10^5))。 接下來m行，每行包括4個正整數u，v，a，b，(1≤u,v≤n，1≤a,b≤10^9)。 最后一行包括2個正整數s，t，(1≤s,t≤n)。

輸出描述:

請你告訴tokitsukaze，在難度為1,2,3,4,5...n時，她的艦隊處于夜戰模式結束游戲受到的最小傷害。

示例1

輸入

復制

4 3 1 4 1 30 1 2 1 10 1 3 20 1 2 3

輸出

復制

2 11 21 33

說明

活動難度為1時，在編號為1的點切換模式，受到的最小傷害為2。 活動難度為2時，在編號為2的點切換模式，受到的最小傷害為11。 活動難度為3時，在編號為3的點切換模式，受到的最小傷害為21。 活動難度為4時，在編號為4的點切換模式，受到的最小傷害為33。

示例2

輸入

復制

4 3 1 4 30 1 1 2 10 1 1 3 20 1 3 1

輸出

復制

1 1 1 51

說明

活動難度為1時，在編號為3的點切換模式，受到的最小傷害為1。 活動難度為2時，在編號為3的點切換模式，受到的最小傷害為1。 活動難度為3時，在編號為3的點切換模式，受到的最小傷害為1。 活動難度為4時，在編號為4的點切換模式，受到的最小傷害為51。路線是3-1-4-1。因為必須處于夜戰模式結束游戲，所以在到達1后還要拐去4去切換模式。

解題報告：
因為有點懶而且比較水所以直接改改官方題解。
s為起點，用邊權a跑一遍最短路，記為disa?。
把邊的方向反轉，t為起點，用邊權b跑一遍最短路，記為disb?。（但是這題是雙向邊所以并不用反轉）
那么在節點?i 切換模式的最小傷害為?disai+disbi，再做一遍后綴min即可。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; struct Edge {int v,ne;ll a,b; } e[MAX]; struct Point {int u;ll c;Point(){}Point(int u,ll c):u(u),c(c){}bool operator<(const Point & b) const {return c > b.c;} }; int tot,head[MAX]; void add(int u,int v,ll a,ll b) {e[++tot].v = v;e[tot].a = a;e[tot].b = b;e[tot].ne = head[u];head[u] = tot; } ll disa[MAX],disb[MAX]; bool vis[MAX]; void Dija(int st,int ed) {memset(disa,0x3f,sizeof disa);memset(vis,0,sizeof vis);priority_queue<Point> pq;pq.push(Point(st,0)); // vis[st] = 1;disa[st] = 0;while(!pq.empty()) {Point cur = pq.top();pq.pop();if(vis[cur.u] == 1) continue;vis[cur.u] = 1;for(int i = head[cur.u]; ~i; i = e[i].ne) {int v = e[i].v;if(vis[v] || disa[v] <= disa[cur.u] + e[i].a) continue;disa[v] = disa[cur.u] + e[i].a;pq.push(Point(v,disa[v]));}} } void Dijb(int st,int ed) {memset(disb,0x3f,sizeof disb);memset(vis,0,sizeof vis);priority_queue<Point> pq;pq.push(Point(st,0)); // vis[st] = 1;disb[st] = 0;while(!pq.empty()) {Point cur = pq.top();pq.pop();if(vis[cur.u] == 1) continue;vis[cur.u] = 1;for(int i = head[cur.u]; ~i; i = e[i].ne) {int v = e[i].v;if(vis[v] || disb[v] <= disb[cur.u] + e[i].b) continue;disb[v] = disb[cur.u] + e[i].b;pq.push(Point(v,disb[v]));}} } ll ans[MAX]; int main() {int n,m,st,ed;memset(head,-1,sizeof head);cin>>n>>m;for(int a,b,c,d,i = 1; i<=m; i++) {scanf("%d%d%d%d",&a,&b,&c,&d);add(a,b,c,d);add(b,a,c,d);}scanf("%d%d",&st,&ed);Dija(st,ed);Dijb(ed,st);ans[n] = disa[n]+disb[n];for(int i = n-1; i>=1; i--) {ans[i] = min(ans[i+1],disa[i]+disb[i]);}for(int i = 1; i<=n; i++) printf("%lld\n",ans[i]);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 1080D】tokitsukaze and Event（最短路，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。