题目链接
题目大意:
对于给你一个有向图,你有两次 *** 作
- 你单前在 u u u点从 u → v urightarrow v u→v花费 1 s 1s 1s
- 你可以把整个图的边都反向!!就是 u → v urightarrow v u→v变成 u ← v uleftarrow v u←v的你第 K K K次 *** 作花费的代价是 2 K − 1 s 2^{K-1}s 2K−1s
问你从1号点到n号点最短时间是多少?
解题思路:
- 首先我们知道如果存在一条路径的话那么最少时间是 n − 1 ( s ) n-1(s) n−1(s)
- 那么 2 18 ≤ 200000 < 2 19 2^{18}leq200000<2^{19} 218≤200000<219,也就是说到了第二个操作了18次操作之后第二个操作的时间就会远远大过第一次操作的时间
- 对于前18次 *** 作我们可以直接分层18层的图跑最短路
- 但是对于大过18次的 *** 作怎么办?,我们知道取模后跑最短路是不对的,那么我们知道对于是第二次 *** 作要尽可能少?那么我们就是对于边开个 < a , b > ( a 表 示 *** 作 2 的 次 数 , b 表 示 *** 作 1 的 次 数 ) (a表示 *** 作2的次数,b表示 *** 作1的次数) (a表示 *** 作2的次数,b表示 *** 作1的次数) 最短路本质也是贪心,可以直接跑。
AC code
#include#define mid ((l + r) >> 1) #define Lson rt << 1, l , mid #define Rson rt << 1|1, mid + 1, r #define ms(a,al) memset(a,al,sizeof(a)) #define log2(a) log(a)/log(2) #define lowbit(x) ((-x) & x) #define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define INF 0x3f3f3f3f #define LLF 0x3f3f3f3f3f3f3f3f #define f first #define s second #define endl 'n' using namespace std; const int N = 2e6 + 10, mod = 998244353; const int maxn = 500010; const long double eps = 1e-5; const int EPS = 500 * 500; typedef long long ll; typedef unsigned long long ull; typedef pair PII; typedef pair PLL; typedef pair PDD; template void read(T &x) { x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f; } template void read(T &first, Args& ... args) { read(first); read(args...); } int n, m; vector G[maxn]; //............................ struct path { int u, tim, val; bool operator < (const path & a) const { return val > a.val; } }; int dp[maxn][20]; bool vis[maxn][20]; inline void dij1() { for(int i = 1; i <= n; ++ i) for(int j = 0; j <= 18; ++ j) dp[i][j] = mod; priority_queue q; dp[1][0] = 0; q.push((path){1,0,0}); while(!q.empty()) { auto top = q.top(); q.pop(); if(vis[top.u][top.tim]) continue; vis[top.u][top.tim] = 1; for(auto it : G[top.u]) { if(it.second != top.tim % 2) { if(top.tim < 18 && dp[it.first][top.tim+1]>dp[top.u][top.tim]+1+(1< top.val+1) { dp[it.first][top.tim] = top.val+1; q.push((path){it.first,top.tim,top.val+1}); } } } } } //...................... struct node { int u, i, v, c; // v是 *** 作2的次数,c是1的 *** 作次数 bool operator < (const node & a) const { if(v != a.v) return v > a.v; else return c > a.c; } }; bool tag[maxn][2]; int v[maxn][2], c[maxn][2]; inline void dij2() { for(int i = 1; i <= n; ++ i) v[i][0] = v[i][1] = c[i][0] = c[i][1] = mod; priority_queue q; for(int i = 1; i <= n; ++ i) // 先把上次的结果继承过来!! if(dp[i][18] != mod) { v[i][0] = 18; c[i][0] = dp[i][18] - (1<<18) + 1; q.push({i,0,v[i][0],c[i][0]}); } while(!q.empty()) { int u = q.top().u; int i = q.top().i; int vq = q.top().v; int cq = q.top().c; q.pop(); if(vis[u][i]) continue; vis[u][i] = 1; for(auto it : G[u]) { if(it.second == i) { if(vq < v[it.first][i] || (vq == v[it.first][i] && 1 + cq < c[it.first][i])) { v[it.first][i] = vq; c[it.first][i] = cq + 1; q.push((node){it.first,i,vq,cq+1}); } } else { if(vq + 1 < v[it.first][i^1] || (vq + 1 == v[it.first][i^1] && 1 + cq < c[it.first][i^1])) { v[it.first][i^1] = vq + 1; c[it.first][i^1] = cq + 1; q.push((node){it.first,i^1,vq+1,cq+1}); } } } } } int pow2[maxn]; int main() { IOS; cin >> n >> m; pow2[0] = 1; for(int i = 1; i <= n; ++ i) pow2[i] = pow2[i-1] * 2 % mod; for(int i = 1; i <= m; ++ i) { int u, v; cin >> u >> v; G[u].push_back({v,0}); G[v].push_back({u,1}); } dij1(); int res = mod; for(int i = 0; i <= 18; ++ i) res = min(res,dp[n][i]); if(res != mod) cout << res; else { // 1 + 2^1 + 2^2..+2^n=2^{n+1}-1 dij2(); if(v[n][0] > v[n][1]) { cout << (1ll * pow2[v[n][1]] - 1 + c[n][1] + mod) % mod; } else { cout << (1ll * pow2[v[n][0]] - 1 + c[n][0] + mod) % mod; } } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)