AtCoderBeginnerContest395E

点我写题 

题意：给个有向图，从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 pare(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(); } }