題目鏈接：點(diǎn)擊查看

題目大意：給出 $n$ 個(gè)點(diǎn)（從 $0$ 開始編號(hào)）和 $m$ 條邊的有向帶權(quán)圖，不過 $m$ 條邊是動(dòng)態(tài)的，經(jīng)過 $t$ 秒后，第 $i$ 條邊就從 $a_i?>b_i,c_i$ 變成了 $a_i?>(b_i+t)\mathrm{m}\mathrm{o}\mathrm{d}n,c_i$，現(xiàn)在要求輸出任意兩點(diǎn)之間的最短路（最短路矩陣）

注意：在達(dá)到某個(gè)點(diǎn)后可以選擇停留任意時(shí)刻再繼續(xù)趕路

題目分析：讀完題后不難建出分層圖最短路的模型，共有 $n?n$ 個(gè)點(diǎn)和 $m?n$ 條邊，直接跑 Floyd 的話是 $O(n^6)$，跑 $n$ 次 Dijkstra 的話是 $O(n?m?n?log(n?n))=O(n^{4}logn)$，所以分層圖的想法只能 pass 了

是賽后看題解補(bǔ)的題，發(fā)現(xiàn)模型很巧妙，如果沒有停留時(shí)間的限制，就是一個(gè)裸的迪杰斯特拉了（不需要分層圖，每個(gè)點(diǎn)貪心松弛即可）

加上了停留時(shí)間的限制，我們可以對(duì)于每個(gè)點(diǎn) $i$ ，添加一條 $i?>(i+1)\mathrm{m}\mathrm{o}\mathrm{d}n,1$
也就是相鄰的兩個(gè)點(diǎn)添加一條花費(fèi)為 $1$ 的道路，為什么這樣建圖是可行的呢？假設(shè)現(xiàn)在點(diǎn) $u$，可以到達(dá)點(diǎn) $v$，若我們想要到達(dá)點(diǎn) $v+k$ 的話，只需要在點(diǎn) $u$ 先等上 $k$ 秒，然后就可以直接走 $u?>(v+k)$ 這條邊了，等效于先走 $u?>v$ 然后每一秒依次走 $v?>v+1$，$v+1?>v+2$ 等等等等

需要注意的是，第一條邊不能走 $i?>i+1$ 這條邊，所以在寫最短路的時(shí)候，我們需要手動(dòng)松弛第一次

還需要注意的是，初始時(shí)可能會(huì)存在重邊（參考樣例二），所以我們初始化鄰接矩陣時(shí)，應(yīng)該將 $i==j$ 的位置也初始化為無窮大才行

因?yàn)檫@個(gè)題目時(shí)間卡的很緊，所以在選擇算法的時(shí)候需要選擇 $O(n^2)$ 的迪杰斯特拉，因?yàn)樵诔砻軋D上跑堆優(yōu)化的迪杰斯特拉，時(shí)間復(fù)雜度是 $O(mlogn)=O(n^{2}logn)$ 的

代碼：

// Problem: F. It's a bird! No, it's a plane! No, it's AaParsa! // Contest: Codeforces - Codeforces Round #722 (Div. 2) // URL: https://codeforces.com/contest/1529/problem/F // Memory Limit: 256 MB // Time Limit: 5000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #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> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const LL inf=0x3f3f3f3f3f3f3f3f; const int N=610; LL maze[N][N],d[N]; bool vis[N]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;read(n),read(m);memset(maze,0x3f,sizeof(maze));while(m--) {int u,v,w;read(u),read(v),read(w);maze[u][v]=w;}for(int i=0;i<n;i++) {memset(d,0x3f,sizeof(d));memset(vis,false,sizeof(vis));for(int j=0;j<n;j++) {d[j]=min(d[j],maze[i][j]);}while(1) {LL mmin=inf;int mark=-1;for(int j=0;j<n;j++) {if(!vis[j]&&(mark==-1||d[j]<mmin)) {mmin=d[j];mark=j;}}if(mark==-1) {break;}vis[mark]=true;d[(mark+1)%n]=min(d[(mark+1)%n],d[mark]+1);for(int j=0;j<n;j++) {d[(j+d[mark])%n]=min(d[(j+d[mark])%n],d[mark]+maze[mark][j]);}}for(int j=0;j<n;j++) {if(i==j) {cout<<0<<' ';} else {printf("%lld ",d[j]);}}puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1529F It‘s a bird! No, it‘s a plane! No, it‘s AaParsa!(最短路+思维建图)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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