ABC-395-E - Flip Edge · znzryb

## 思路讲解

类似于最短路问题。但这题真的难度只有977吗？这个1400多的树上dp我都有点思路。这个是看完一点思路都没有呀。

不过图论嘛有什么难的那？我很快想到了分层图。这个其实把这张图分为两层就可以了，一层正图，一层反图，正图到反图或者反图到正图都有代价X。

其实dijsktra的关键在于是去找点，就是说目前为止找到的不确定点（dist=INF）中与原点最近的点，改为确定点就（dist=dis）好了。

## AC代码

[https://atcoder.jp/contests/abc395/submissions/64132524](https://atcoder.jp/contests/abc395/submissions/64132524)

```cpp
// Problem: E - Flip Edge
// Contest: AtCoder - AtCoder Beginner Contest 395
// URL: https://atcoder.jp/contests/abc395/tasks/abc395_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,X,T,A[MAXN];
vector<ll> g[MAXN];
ll dist[MAXN];

struct cmp{
	bool operator()(const arr &a,const arr &b)const{
		return a[1]>b[1];
	}
};

inline void solve(){
	cin>>N>>M>>X;
	FOR(i,1,2*N){
		dist[i]=INF;
	}
	FOR(i,1,M){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v+N].pb(u+N);
	}
	priority_queue<arr,vector<arr>,cmp> pq;
	pq.push({1,0});
	while(!pq.empty()){
		ll node=pq.top()[0],dis=pq.top()[1];
		pq.pop();
		if(dist[node]==INF){
			dist[node]=dis;
			FOR(i,0,SZ(g[node])-1 ){
				ll toNode=g[node][i];
				pq.push({toNode,dis+1});
			}
			if(node>N){
				pq.push({node-N,dis+X});
			}else{
				pq.push({node+N,dis+X});
			}
		}
	}
	cout<<min(dist[N],dist[2*N])<<"\n";
// #ifdef LOCAL
    // FOR(i,1,2*N){
    	// cerr<<dist[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc395/submissions/64132524
*/
```

## 心路历程（WA，TLE，MLE……）