package yukicoder020; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int v=sc.nextInt(); int ox=sc.nextInt()-1; int oy=sc.nextInt()-1; int[][] map=new int[n][n]; for(int i=0;i=0&&oy>=0){ long tmp=di.getShortestPath(0, ox+oy*n); if(tmp[] edges; PriorityQueue pq; int n; int s; final long INF=Long.MAX_VALUE; Dijkstra(int n){ this.n=n; edges=new List[n]; for(int ii=0;ii(); } s=-1; } public void addEdge(int i,int j,int c){ edges[i].add(new Edge(i,j,c)); } public long getShortestPath(int i,int j){ if(s!=i){ d=new long[n]; Arrays.fill(d, INF); d[i]=0;//the min total cost to go to i pq=new PriorityQueue(); pq.add(new Vertex(i,d[i])); while(!pq.isEmpty()){ Vertex u=pq.poll(); if(d[u.me]d[u.me]+v.w){ d[v.v]=d[u.me]+v.w; pq.add(new Vertex(v.v,d[v.v])); } } } s=i; } return d[j]; } private static class Edge{ //int u;//from int v;//to int w;//cost Edge(int u,int v,int w){ // u=this.u; this.v=v; this.w=w; } } public static class Vertex implements Comparable{ int me;//me long d;//cost(the min total cost to arrive here) Vertex(int me,long d){ this.me=me; this.d=d; } @Override public int compareTo(Vertex o){ return Long.compare(this.d, o.d); // return this.d>o.d?1:this.d