图论 ---- C. Graph Transpositions（数据分阶段分层图最短路(二维) + 贪心）

图论 ---- C. Graph Transpositions（数据分阶段分层图最短路(二维) + 贪心）

题目链接

---

题目大意：

对于给你一个有向图，你有两次 *** 作

1. 你单前在 u u u点从 u → v urightarrow v u→v花费 1 s 1s 1s
2. 你可以把整个图的边都反向！！就是 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号点最短时间是多少？

---

解题思路：

1. 首先我们知道如果存在一条路径的话那么最少时间是 n − 1 ( s ) n-1(s) n−1(s)
2. 那么 2 18 ≤ 200000 < 2 19 2^{18}leq200000<2^{19} 218≤200000<219，也就是说到了第二个操作了18次操作之后第二个操作的时间就会远远大过第一次操作的时间
3. 对于前18次 *** 作我们可以直接分层18层的图跑最短路
4. 但是对于大过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;
}