結果
| 問題 |
No.340 雪の足跡
|
| コンテスト | |
| ユーザー |
 holeguma
|
| 提出日時 | 2016-01-29 23:12:23 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,009 bytes |
| コンパイル時間 | 2,816 ms |
| コンパイル使用メモリ | 87,468 KB |
| 実行使用メモリ | 129,080 KB |
| 最終ジャッジ日時 | 2024-09-21 18:38:52 |
| 合計ジャッジ時間 | 8,766 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 3 |
| other | AC * 4 WA * 11 TLE * 1 -- * 16 |
ソースコード
import java.io.InputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.math.BigInteger;
public class Main{
static PrintWriter out;
static InputReader ir;
static void solve(){
int w=ir.nextInt(),h=ir.nextInt(),n=ir.nextInt();
int[] d={w,-1,-w,1};
G g=new G(w*h,false);
boolean[][] ag=new boolean[w*h][4];
while(n-->0){
int m=ir.nextInt();
int[] b=ir.nextIntArray(m+1);
for(int i=0;i<m;i++){
if(Math.abs(b[i]-b[i+1])>=w){
int e=Math.abs(b[i]-b[i+1])/w;
if(b[i]>b[i+1]){
for(int j=0;j<e;j++){
ag[b[i]-w*j][2]=true;
ag[b[i]-w*(j+1)][0]=true;
}
}
else{
for(int j=0;j<e;j++){
ag[b[i]+w*j][0]=true;
ag[b[i]+w*(j+1)][2]=true;
}
}
}
else{
int e=Math.abs(b[i]-b[i+1]);
if(b[i]>b[i+1]){
for(int j=0;j<e;j++){
ag[b[i]-j][1]=true;
ag[b[i]-(j+1)][3]=true;
}
}
else{
for(int j=0;j<e;j++){
ag[b[i]+j][3]=true;
ag[b[i]+j+1][1]=true;
}
}
}
}
}
for(int i=0;i<h*w;i++){
for(int j=0;j<4;j++){
if(ag[i][j]) g.addEdge(i,i+d[j]);
}
}
int[] dist=g.dijkstra(0);
if(dist[h*w-1]==1<<26) out.println("Odekakedekinai..");
else out.println(dist[h*w-1]);
}
static class G{
AL[] g,rg;
private int V;
private boolean ndir;
public G(int V,boolean ndir){
this.V=V;
this.ndir=ndir;
g=new AL[V];
for(int i=0;i<V;i++) g[i]=new AL();
}
public void addEdge(int u,int v,int t){
g[u].add(new int[]{v,t});
if(this.ndir) g[v].add(new int[]{u,t});
}
public void addEdge(int u,int v){
addEdge(u,v,0);
}
public int to(int from,int ind){return g[from].get(ind)[0];}
public int cost(int from,int ind){return g[from].get(ind)[1];}
public int[] dijkstra(int s){
int[] dist=new int[this.V];
java.util.PriorityQueue<int[]> pque=new java.util.PriorityQueue<int[]>(11,new Comparator<int[]>(){
public int compare(int[] a,int[] b){
return Integer.compare(a[0],b[0]);
}
});
Arrays.fill(dist,1<<26);
dist[s]=0;
pque.offer(new int[]{0,s});
while(!pque.isEmpty()){
int[] p=pque.poll();
int v=p[1];
if(dist[v]<p[0]) continue;
for(int i=0;i<g[v].size();i++){
int to=to(v,i),cost=cost(v,i);
if(dist[to]>dist[v]+cost){
dist[to]=dist[v]+cost;
pque.offer(new int[]{dist[to],to});
}
}
}
return dist;
}
public int[] tporder(){
boolean[] vis=new boolean[V];
ArrayList<Integer> ord=new ArrayList<>();
for(int i=0;i<V;i++) if(!vis[i]) ts(i,vis,ord);
int[] ret=new int[V];
for(int i=ord.size()-1;i>=0;i--) ret[ord.size()-1-i]=ord.get(i);
return ret;
}
public int[] scc(){
rg=new AL[V];
for(int i=0;i<V;i++) rg[i]=new AL();
int from,to;
for(int i=0;i<V;i++){
for(int j=0;j<g[i].size();j++){
to=i;
from=to(i,j);
rg[from].add(new int[]{to,0});
}
}
int[] ord=tporder();
int k=0;
boolean[] vis=new boolean[V];
int[] ret=new int[V+1];
for(int i=0;i<V;i++) if(!vis[i]) rs(ord[i],vis,ret,k++);
ret[V]=k;
return ret;
}
private void ts(int now,boolean[] vis,ArrayList<Integer> ord){
vis[now]=true;
int to;
for(int i=0;i<g[now].size();i++){
to=to(now,i);
if(!vis[to]) ts(to,vis,ord);
}
ord.add(now);
}
private void rs(int now,boolean[] vis,int[] ret,int k){
vis[now]=true;
ret[now]=k;
int to;
for(int i=0;i<rg[now].size();i++){
to=rg[now].get(i)[0];
if(!vis[to]) rs(to,vis,ret,k);
}
}
static class AL extends ArrayList<int[]>{};
}
public static void main(String[] args) throws Exception{
ir=new InputReader(System.in);
out=new PrintWriter(System.out);
solve();
out.flush();
}
static class InputReader {
private InputStream in;
private byte[] buffer=new byte[1024];
private int curbuf;
private int lenbuf;
public InputReader(InputStream in) {this.in=in; this.curbuf=this.lenbuf=0;}
public boolean hasNextByte() {
if(curbuf>=lenbuf){
curbuf= 0;
try{
lenbuf=in.read(buffer);
}catch(IOException e) {
throw new InputMismatchException();
}
if(lenbuf<=0) return false;
}
return true;
}
private int readByte(){if(hasNextByte()) return buffer[curbuf++]; else return -1;}
private boolean isSpaceChar(int c){return !(c>=33&&c<=126);}
private void skip(){while(hasNextByte()&&isSpaceChar(buffer[curbuf])) curbuf++;}
public boolean hasNext(){skip(); return hasNextByte();}
public String next(){
if(!hasNext()) throw new NoSuchElementException();
StringBuilder sb=new StringBuilder();
int b=readByte();
while(!isSpaceChar(b)){
sb.appendCodePoint(b);
b=readByte();
}
return sb.toString();
}
public int nextInt() {
if(!hasNext()) throw new NoSuchElementException();
int c=readByte();
while (isSpaceChar(c)) c=readByte();
boolean minus=false;
if (c=='-') {
minus=true;
c=readByte();
}
int res=0;
do{
if(c<'0'||c>'9') throw new InputMismatchException();
res=res*10+c-'0';
c=readByte();
}while(!isSpaceChar(c));
return (minus)?-res:res;
}
public long nextLong() {
if(!hasNext()) throw new NoSuchElementException();
int c=readByte();
while (isSpaceChar(c)) c=readByte();
boolean minus=false;
if (c=='-') {
minus=true;
c=readByte();
}
long res = 0;
do{
if(c<'0'||c>'9') throw new InputMismatchException();
res=res*10+c-'0';
c=readByte();
}while(!isSpaceChar(c));
return (minus)?-res:res;
}
public double nextDouble(){return Double.parseDouble(next());}
public BigInteger nextBigInteger(){return new BigInteger(next());}
public int[] nextIntArray(int n){
int[] a=new int[n];
for(int i=0;i<n;i++) a[i]=nextInt();
return a;
}
public long[] nextLongArray(int n){
long[] a=new long[n];
for(int i=0;i<n;i++) a[i]=nextLong();
return a;
}
public char[][] nextCharMap(int n,int m){
char[][] map=new char[n][m];
for(int i=0;i<n;i++) map[i]=next().toCharArray();
return map;
}
}
}