AtCoder Beginner Contest 395 E

点我写题 

题意：给个有向图，从1出发，每次可以走一条有向边，花费为1，也可以选择把全部有向边翻转，花费x，问到n的最小花费

思路：最短路+dp，定义dis[i][0/1]表示走到i为止，用了翻转操作（0/1）次的最少代价（为啥总是取值0/1呢，因为翻转了偶数次就相当于翻回去了），如果当前状态是走到当前点翻转了奇数次，那么我当前点就只能走相邻的编号为1的边（当然这个编号是我自己定义的，0表示原边，1表示反边，也就是建了一个无向图，然后用编号区分），转移的话就是对+1操作取min（可以看下面代码），特殊的是对自己这个点来说，我能在原地用翻转操作，这样就是对+x取min，然后状态要取反。

os:我个人觉得这个实现还是比较优美的，不用建奇奇怪怪的分层图，这题有点像第十四届蓝桥杯java b组的最后一题，所以思路比较快能想到。

import java.util.*;
import java.io.*;
public class Main{public static BufferedReader rd=new BufferedReader(new InputStreamReader(System.in));public static BufferedWriter wd=new BufferedWriter(new OutputStreamWriter(System.out));public static int n,m,x;public static long dis[][];public static boolean has[][];public static ArrayList<pair>sk[];public static class pair implements Comparable<pair>{int fi,se;pair(int fi,int se){this.fi=fi;this.se=se;}public int compareTo(pair b){return Long.compare(dis[fi][se],dis[b.fi][b.se]);}}public static void dijkstra(){for(int i=1;i<=n;i++) Arrays.fill(dis[i],(long)1e18);dis[1][0]=0;dis[1][1]=x;PriorityQueue<pair>dl=new PriorityQueue<>();dl.add(new pair(1,0));dl.add(new pair(1,1));while(dl.isEmpty()==false){pair nw=dl.poll();int u=nw.fi,st=nw.se;if(has[u][st]) continue;has[u][st]=true;if(dis[u][st^1]>dis[u][st]+x){dis[u][st^1]=dis[u][st]+x;dl.add(new pair(u,st^1));}for(pair v:sk[u]){if(v.se!=st) continue;if(dis[v.fi][st]>dis[u][st]+1){dis[v.fi][st]=dis[u][st]+1;dl.add(new pair(v.fi,st));}}}}public static void main(String args[])throws Exception{String dr[]=rd.readLine().split(" ");n=Integer.parseInt(dr[0]);m=Integer.parseInt(dr[1]);x=Integer.parseInt(dr[2]);dis=new long [n+10][3];sk=new ArrayList [n+10];has=new boolean [n+10][3];for(int i=1;i<=n;i++) sk[i]=new ArrayList<>();for(int i=1;i<=m;i++){dr=rd.readLine().split(" ");int u=Integer.parseInt(dr[0]),v=Integer.parseInt(dr[1]);sk[u].add(new pair(v,0));sk[v].add(new pair(u,1));}dijkstra();//  for(int i=1;i<=n;i++) wd.write(i+" "+dis[i][0]+" "+dis[i][1]+"\n");wd.write(Math.min(dis[n][0],dis[n][1])+"");wd.flush();}
}