題目鏈接
https://codeforces.com/contest/1694/problem/E
題意簡述
\(Keshi\) 準備從城市 \(1\) 出發,前往 \(AmShZ\) 所在的城市 \(n\) .這里一共有 \(n\) 個城市 ,編號 \(1 \sim n\),有 \(m\) 條有向道路. \(Keshi\) 不知道城市的路線,他需要聽從 \(AmShZ\) 的指揮.
每一天的開始, \(AmShZ\) 告訴 \(Keshi\) 以下兩條信息之一
- 告訴他一個阻擋的道路 ,之后 \(Keshi\) 將永遠不會走這條道路,并且他會留在他當前所在的城市一天
- 讓 \(Keshi\) 開始移動 , \(Keshi\) 將會隨機選擇一條路線移動到附近的一個可以到達的相鄰的城市.如果無路可走,他將留在當前城市
現在告訴你城市和道路的數量,以及各個道路的起始點和終點
請你告訴他們最少需要多少天能保證 \(Keshi\) 一定可以到達 \(AmShZ\) 所在的城市
樣例
點擊查看樣例
分析
為了避免引起混淆提前說一下:
一條由 \(a\) \(\rightarrow\) \(b\) 的邊,下稱 \(a\) 是這條邊的起始點 ,\(b\)是這條邊的結束點
圖中第一次走的起始點稱為起點,目的地稱為終點.
這個題一開始想的就是從起點開始走,走任何一條邊的一次的花費等于這條邊的起始點的出度\(-1\) (封堵其他路徑的花費)+ \(1\) \((\) 從起始點走到結束點花費一天 \()\).用 \(dist[i]\) 記錄 從起點 \(1\) 走到 \(i\) 的最小花費天數,然后愉快的WA16了.
想了很久,搜了很多題解,仍然沒想出哪錯了..
其實走的過程中有些路徑是不用刪的,而這種情況是我們從前往后走所無法考慮到(或者說無法判斷出)的.
看下面這張圖:
從 \(1\) 到 \(n\) 的距離最小很顯然是 \(2\) ,一條邊都不用刪 .而如果采用我們剛才想的那個刪邊策略,從 \(1\) 出發走到下一個點 ,無論是哪個,都要刪掉兩個邊,白白的浪費了 \(2\) 天,最后結果是 \(3\) ,比正確答案偏大了.
因此,我們刪邊的時候還應該考慮到當前邊的結束點到結點 \(n\) 的距離長短以確保不會出現浪費次數的情況.正著走顯然是無法解決的.那么我們看看反向建圖能不能解決這個問題.
從點 \(n\) 開始往前走 ,每一次取出距離點 \(n\) 最近的點 \(x\) ,用它來更新與 \(x\) 相鄰的點到 \(n\) 的距離 .用 \(dis[i]\) 表示點 \(i\) 走到點 \(n\) 最小的無論怎么走一定能走到 \(n\) 的所需花費的天數
考慮下面這種情況
中間這些點到 \(n\) 的距離分別為 $1\ 3\ 8\ $,那么 \(dis[v]\) 就要被這三個點更新
(為了方便起見我們把中間這三個點從下往上編號 \(2\ 3\ 4\))
首先對于 \(dis=1\)的 \(2\) 號點來說, 想用 \(dis[2]\) 來更新 \(dis[v]\) 的話,為了保證 \(v\) 無論怎么走一定能在這個步數內到 \(n\) ,需要把與 \(v\) 相鄰的 \(dis\) 比 \(dis[2]\)大的點所連的邊刪掉. 那么 從 \(2\) 走到 \(v\) 的花費天數 \(dist=dis[2]+din[v]-1+1\)(即使從 \(2\) 到 \(v\) 有重邊也不會影響答案的正確性,因為我們對重邊也會全都遍歷到,那么 din[y] 也會隨之改變 ,下面會講到)
對于 \(dis=3\)的 \(3\) 號點來說, 想用 \(dis[3]\) 來更新 \(dis[v]\) 的話,為了保證 \(v\) 無論怎么走一定能在這個步數內到 \(n\) ,需要把與 \(v\) 相鄰的 \(dis\) 比 \(dis[2]\)大的點所連的邊刪掉,即\(3\ 4\) 號點, 那么 從 \(2\) 走到 \(v\) 的花費天數 \(dist=dis[2]+din[v]-2+1\) (結點 \(2\) 的dis更小,不用刪結點 \(2\) 的邊 ,所以花費天數比 \(2\) 號點少一天)
那么我們如果當前結點能走到 \(v\) 時,由于我們使用了優先隊列,顯然每次取出的點要么無法到達 \(v\) ,要么是距離 \(v\) 是當前最近的(當然肯定也是未訪問過的點),更新完 \(dis[v]\) ,再讓 \(dis[v]--\) , 就能保證與 \(v\) 相連的點更新 \(dis[v]\) 時的時間花費是合理的.就直接是\(dis[v]=min(dis[v],dis[u]+din[i])\) 不用額外的減什么東西了.
代碼
點擊查看第一次正向建圖遍歷的錯誤代碼
#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int e[N],ne[N],idx,h[N];
int dout[N],din[N];
unordered_map<int,int>mp[N];
typedef pair<LL,int>PII;
priority_queue<PII,vector<PII>,greater<PII> > q;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
LL dis[N];
int vis[N];
LL dijkstra()
{
memset(dis,0x4f,sizeof dis);
dis[1]=0;
q.push({0,1});
while(q.size())
{
auto t=q.top();
q.pop();
int i=t.second;
if(vis[i])continue;
vis[i]=1;
for(int j=h[i];j!=-1;j=ne[j])
{
int k=e[j];
LL dist=dis[i]+dout[i];
if(mp[i][k]>1)
{
dist-=(mp[i][k]-1);
}
if(dis[k]>dist)
{
dis[k]=dist;
q.push({dis[k],k});
}
}
}
return dis[n];
}
int main()
{
//freopen("uva.txt","r",stdin);
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(mp[a].find(b)==mp[a].end())
{
mp[a][b]=1;
add(a,b);
}else mp[a][b]++;
dout[a]++;
}
printf("%lld\n",dijkstra());
return 0;
}
點擊查看AC代碼
#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int e[N],ne[N],idx,h[N];
int dout[N],din[N];
unordered_map<int,int>mp[N];
typedef pair<LL,int>PII;
priority_queue<PII,vector<PII>,greater<PII> > q;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
LL dis[N];
int vis[N];
LL dijkstra()
{
memset(dis,0x4f,sizeof dis);
dis[n]=0;
q.push({0,n});
while(q.size())
{
auto t=q.top();
q.pop();
int i=t.second;
if(vis[i])continue;
vis[i]=1;
for(int j=h[i];j!=-1;j=ne[j])
{
int k=e[j];
LL dist=dis[i]+din[k];
if(dis[k]>dist)
{
dis[k]=dist;
q.push({dist,k});
}
din[k]--;
}
}
return dis[1];
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(b,a);
din[a]++;
}
printf("%lld\n",dijkstra());
return 0;
}
