Submission

(PPPP)(PPPPPP)(PPPPPPTTTT)

Score: 80

User: hmmm

Problemset: ย้อนศร

Language: cpp

Time: 0.796 second

Submitted On: 2025-01-09 16:48:10

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ppi=array<int,3>;
const int N=1e5+5;
vector<pii> g[N],rev[N];
int dis[2][N];
int vis[2][N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin >> u >> v;
		g[u].push_back({v,0});
		rev[v].push_back({u,1});
	}
	int t;
	cin >> t;
	while(t--){
		int u,v;
		cin >> u >> v;
		priority_queue<ppi,vector<ppi>,greater<ppi>> q;
		for(int i=1;i<=n;i++){
			dis[0][i]=dis[1][i]=1e9;
			vis[0][i]=vis[1][i]=false;
		}
		q.push({dis[0][u]=0,u,0});
		while(!q.empty()){
			auto l=q.top()[0];
			auto x=q.top()[1];
			auto st=q.top()[2];
			q.pop();
			if(x==v){
				cout << l << "\n";
				break;
			}
//			cout << l << ' ' << x << ' ' << st << "\n";
			if(vis[st][x]) continue;
			vis[st][x]=true;
			for(auto e:g[x]){
				auto xx=e.first;
				auto ll=e.second;
//				cout << xx << "-\n";
//				cout << dis[st][xx] << ' ' << dis[st][xx]+ll << '\n';
				if(dis[st][xx]>dis[st][x]+ll){
					dis[st][xx]=dis[st][x]+ll;
					q.push({dis[st][xx],xx,st});
//					cout << "a\n";
				}
			}
			for(auto e:rev[x]){
				auto xx=e.first;
				auto ll=e.second;
//				cout << xx << "--\n";
//				cout << dis[1][xx] << ' ' << dis[1][xx]+ll << '\n';	
				if(dis[1][xx]>dis[st][x]+ll){
					dis[1][xx]=dis[st][x]+ll;
					q.push({dis[1][xx],xx,1});
//					cout << "aa\n";
				}				
			}
		}
	}
}