CF449B Jzzhu and Cities

其實(shí)這一道題并不是很難，只是一個(gè)最短路而已，請(qǐng)繼續(xù)看我的題解吧~(^▽^)

AC代碼：

#include<bits/stdc++.h> #define maxn 3000005 #define pa pair<long long,long long> #define inf 1000000000000000000ll using namespace std; long long n,m,k; struct edge{long long val,to; }; bool vis[maxn]; long long dis[maxn],mark[maxn]; priority_queue<pa,vector<pa>,greater<pa> > q; vector<edge> e[maxn*3]; long long ans; void dijkstra() {memset(vis,0,sizeof(vis));dis[1]=0;q.push(make_pair(0,1));while(!q.empty()){int x=q.top().second;q.pop();if(vis[x])continue;vis[x]=1;for(int i=0;i<e[x].size();i++){int y=e[x][i].to;if(dis[x]+e[x][i].val<=dis[y]){if(mark[y]){mark[y]=0;}if(dis[x]+e[x][i].val<dis[y]){dis[y]=dis[x]+e[x][i].val;q.push(make_pair(dis[y],y));}}}} } void addedge(long long x,long long y,long long v){edge tmp;tmp.to=y;tmp.val=v;e[x].push_back(tmp); } int main() {scanf("%lld%lld%lld",&n,&m,&k);for(int i=1;i<=n;i++)dis[i]=inf;for(int i=1;i<=m;i++){long long x,y,z;scanf("%lld%lld%lld",&x,&y,&z);addedge(x,y,z);addedge(y,x,z);}for(int i=1;i<=k;i++){long long y,z;scanf("%lld%lld",&y,&z);if(dis[y]>z){dis[y]=z;q.push(make_pair(z,y));mark[y]=1;}}dijkstra();for(int i=1;i<=n;i++)ans+=mark[i];printf("%lld\n",k-ans);}

詳解

那么我們來簡化一下題目的含義
就是說有n個(gè)城市
1號(hào)城市是起點(diǎn)（樹的根）
有m條普通邊
有k條特殊邊
問最多能刪掉多少條邊，能使最短路徑不變

那么我們就可以先把n+k條邊跑一遍dijkstra
然后就求出來了每個(gè)城市之間的最短路
在跑最短路的過程中判斷這k條特殊邊是否去掉后不影響最短路

但是這個(gè)題還有一個(gè)很坑人的bug
就像樣例2中的一樣，那k條特殊邊可能會(huì)重復(fù)
那其實(shí)我們只需要留下來一條最短的就行了
用這個(gè)最短的一條去構(gòu)建最短路
剩下的就直接刪掉了
最后只需要用總邊數(shù)減去剩余的特殊邊的數(shù)量就行啦!~

轉(zhuǎn)載于:https://www.cnblogs.com/Tidoblogs/p/11222636.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的CF449B Jzzhu and Cities 迪杰斯特拉最短路算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。