題目鏈接

http://codeforces.com/contest/576/problem/D

題解

把邊按\(t_i\)從小到大排序后枚舉\(i\), 求出按前\((i-1)\)條邊走\(t_i\)步能到達的點的集合，以它們為起點求\(n\)號點的最短路。
前者等于前\((i-2)\)條邊走\(t_{i-1}\)步能到達的點集乘上前\((i-1)\)條邊鄰接矩陣的\((t_i-t_{i-1})\)次冪。
因為只關心是否存在，故可以使用bitset優化。
時間復雜度\(O(mn^3+\frac{n^3\log T}{\omega})\).

代碼

#include<bits/stdc++.h> using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(;!isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int N = 150; const int INF = 2e9; struct AEdge {int u,v,t;bool operator <(const AEdge &arg) const {return t<arg.t;} } ae[N+3]; struct Edge {int v,nxt; } e[(N<<1)+3]; int a[N+3]; int fe[N+3]; int que[N+3]; int dep[N+3]; bool vis[N+3]; int n,m,en;void addedge(int u,int v) {en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en; }struct Matrix {bitset<N+3> a[N+3];Matrix() {for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) a[i][j] = 0;}Matrix operator *(const Matrix &arg) const{Matrix ret;for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(a[i][j]) {ret.a[i]|=arg.a[j];}}}return ret;} }; Matrix I,O,g,b;void clearedge() {for(int i=1; i<=n; i++) fe[i] = 0;for(int i=1; i<=en; i++) e[i].v = e[i].nxt = 0;en = 0; }Matrix mquickpow(Matrix x,int y) {Matrix cur = x,ret = I;for(int i=0; y; i++){if(y&(1<<i)) {y-=(1<<i); ret = ret*cur;}cur = cur*cur;}return ret; }void bfs() {for(int i=1; i<=n; i++) vis[i] = false;int hd = 1,tl = 0;for(int i=1; i<=n; i++) {if(g.a[1][i]) {tl++; que[tl] = i; vis[i] = true; dep[i] = 0;}}while(hd<=tl){int u = que[hd]; hd++;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(!vis[v]) {vis[v] = true; tl++; que[tl] = v; dep[v] = dep[u]+1;}}} }int main() {scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) I.a[i].set(i);for(int i=1; i<=m; i++){scanf("%d%d%d",&ae[i].u,&ae[i].v,&ae[i].t);}sort(ae+1,ae+m+1);g = I;int ans = INF;for(int i=1; i<=m; i++){for(int j=1; j<=i; j++) {addedge(ae[j].u,ae[j].v);}g = g*mquickpow(b,ae[i].t-ae[i-1].t);bfs();if(vis[n]) {ans = min(ans,ae[i].t+dep[n]);}clearedge();b.a[ae[i].u].set(ae[i].v);}if(ans==INF) puts("Impossible");else printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 576D Flights for Regular Customers (图论、矩阵乘法、Bitset)的全部內容，希望文章能夠幫你解決所遇到的問題。

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