題目鏈接：點擊查看
題目大意：給出一個由 n 個點和 m 條邊組成的有向圖，現在有一個人，他有一條固定的路線，這個題目中有一個導航，當到達任意一個點時，導航都會給出一條通往終點的最短路，但是這個人固定的路線并不一定每次都是最短路，導航最初會給出一條最短路，如果這個人不按照最短路行走的話，那么導航需要“重構”最短路，題目問“重構”的最小次數和最大次數
題目分析：其實讀完題后，首先第一反應是先將所有的邊置反，然后對于終點求一次迪杰斯特拉，因為這是CF，怕hack，所以盡量還是別用spfa吧，然后題目給出的固定路線中有 k 個點，即?k - 1 條邊，對于每條邊判斷，無非只有三種情況，我們記ans0為最小次數，ans1為最大次數：設這條邊為 u -> v
當前邊不是最短路上的邊，那么無論如何走，從點 u 到點 v 后，導航一定會重構一次最短路，那么ans0++,ans1++ 當前邊是最短路上的邊，顯然ans0不變，因為選擇當前路就可以使得最短路最短，且無需重構 如果當前邊是最短路的必經邊，也就是從點 u 到終點只有 u ->v 這一條最短路滿足路程最短，ans1不變，因為沒有其他選擇了 如果當前邊不是最短路的必經邊，那么必然存在另一條邊 u -> t 滿足點 u 到終點的距離仍然是最短路，此時選擇 u -> t 這條路可以使ans1++
然后直接模擬上述三種情況就好了，為了方便書寫，迪杰斯特拉我用了鏈式前向星的模板，建立反向邊，而正向邊仍然用鄰接表儲存，用于最后統計答案時用
代碼：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;//頂點數 const int M=2e5+100;//邊數struct Edge
{int to,w,next;
}edge[M];int head[N],d[N],cnt;//鏈式前向星 bool vis[N];void addedge(int u,int v,int w)
{edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}struct Node
{int to,w;Node(int TO,int W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;}
};void Dijkstra(int st)
{priority_queue<Node>q;memset(vis,false,sizeof(vis));memset(d,inf,sizeof(d));d[st]=0;q.push(Node(st,0));while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//掃描出所有邊 {int v=edge[i].to;int w=edge[i].w;if(d[v]>d[u]+w)//更新 {d[v]=d[u]+w;q.push(Node(v,d[v]));}}}
}void init()
{memset(head,-1,sizeof(head));cnt=0;
}vector<int>node[N];int a[N];int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);init();int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);addedge(v,u,1);}int k;scanf("%d",&k);for(int i=1;i<=k;i++)scanf("%d",a+i);Dijkstra(a[k]);int ans_0=0,ans_1=0;int u=a[1];int dis=d[u];for(int i=2;i<=k;i++){int v=a[i];if(d[u]!=d[v]+1)//新加的邊不在最短路上{ans_1++,ans_0++;}else//在最短路上{for(auto vv:node[u]){if(vv==v)continue;if(d[u]==d[vv]+1){ans_1++;break;}}}u=v;}printf("%d %d\n",ans_0,ans_1);}
?
總結
以上是生活随笔 為你收集整理的CodeForces - 1321D Navigation S.ystem(最短路+思维) 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
