結果
| 問題 | No.92 逃走経路 |
| ユーザー |
 Asahi
|
| 提出日時 | 2023-10-02 11:50:17 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 133 ms / 5,000 ms |
| コード長 | 12,177 bytes |
| コンパイル時間 | 3,010 ms |
| コンパイル使用メモリ | 92,512 KB |
| 実行使用メモリ | 44,356 KB |
| 最終ジャッジ日時 | 2024-07-26 13:42:27 |
| 合計ジャッジ時間 | 5,668 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 123 ms
43,252 KB |
| testcase_01 | AC | 69 ms
38,204 KB |
| testcase_02 | AC | 71 ms
38,264 KB |
| testcase_03 | AC | 72 ms
38,200 KB |
| testcase_04 | AC | 72 ms
38,296 KB |
| testcase_05 | AC | 123 ms
40,592 KB |
| testcase_06 | AC | 109 ms
39,968 KB |
| testcase_07 | AC | 116 ms
39,536 KB |
| testcase_08 | AC | 101 ms
43,788 KB |
| testcase_09 | AC | 109 ms
44,356 KB |
| testcase_10 | AC | 124 ms
41,876 KB |
| testcase_11 | AC | 126 ms
42,564 KB |
| testcase_12 | AC | 126 ms
43,872 KB |
| testcase_13 | AC | 104 ms
43,252 KB |
| testcase_14 | AC | 104 ms
43,100 KB |
| testcase_15 | AC | 116 ms
43,212 KB |
| testcase_16 | AC | 117 ms
42,996 KB |
| testcase_17 | AC | 132 ms
42,956 KB |
| testcase_18 | AC | 133 ms
41,460 KB |
| testcase_19 | AC | 122 ms
40,696 KB |
ソースコード
import java.util.*;
import java.io.*;
class Main implements Runnable
{
//その時の思考をここに書く
/*
*
*/
record Edge(int to , int cost ) { }
record State(int now , int idx) { }
void solve()
{
int N = in.nextInt() , M = in.nextInt() , K = in.nextInt();
List<Edge> [] G = new ArrayList[N];
for(int i = 0 ; i < N ; i ++ )
{
G[i] = new ArrayList<>();
}
for(int i = 0 ; i < M ; i ++ )
{
int a = in.nextInt() , b = in.nextInt() , c = in.nextInt();
--a;--b;
G[a].add(new Edge(b ,c));
G[b].add(new Edge(a, c));
}
int [] d = in.IntArray(K);
boolean [][] dp = new boolean[K + 1][N];
for(int i = 0 ; i < N ; i ++ ) dp[0][i] = true;
for(int i = 0 ; i < K ; i ++ )
{
for(int j = 0 ; j < N ; j ++ )
{
for(Edge k : G[j])
{
if(k.cost == d[i]) dp[i + 1][k.to] |= dp[i][j];
}
}
}
TreeSet<Integer> ans = new TreeSet<>();
for(int i = 0 ; i < N ; i ++ ) if(dp[K][i]) ans.add(i + 1);
out.println(ans.size());
for(int v : ans) out.print(v+" ");
}
public static void main(String[] args)
{
new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start();
}
public void run()
{
solve();
out.flush();
}
record ip(int fi , int se) { public String toString() { return fi +" "+ se ;} }
record lp(long fi , long se) { public String toString() { return fi +" "+ se ;} }
public double dist(lp p1 , lp p2) { return Math.sqrt((p1.fi - p2.fi) * (p1.fi - p2.fi) + (p1.se - p2.se) * (p1.se - p2.se)); }
public int max(int ... a) { int max = -1 ; for(int p : a) max = Math.max(max , p); return max; }
public int min(int ... a) { int min = Integer.MAX_VALUE ; for(int p : a) min = Math.min(min , p); return min; }
public long max(long ... a) { long max = -1 ; for(long p : a) max = Math.max(max , p); return max; }
public long min(long ... a) { long min = Long.MAX_VALUE ; for(long p : a) min = Math.min(min , p); return min; }
public int sum(int ... a) { int sum = 0 ; for(int p : a) sum += p ; return sum ;}
public long sum(long ... a) { long sum = 0 ; for(long p : a) sum += p ; return sum ;}
public int abs(int a , int b) { return (int) Math.abs(a - b) ; }
public long abs(long a , long b) { return (long) Math.abs(a - b) ; }
public int pow(int a , int b) { return (int) Math.pow(a , b) ; }
public long pow(long a , long b) { return (long) Math.pow(a , b) ; }
public long rec(long a) { return a == 1 ? 1 : a * rec(a - 1); }
public long [] recmod(int a , long MOD) { long [] recMod = new long[1 << 17] ; recMod[1] = 1 ; for(int i = 2 ; i < (1 << 17) ; i ++ ) recMod[i] = (recMod[i - 1] * i) % MOD9; return recMod; }
public int [] rev(int [] a) { int [] r = new int[a.length] ; int idx = a.length ; for(int p : a) r[--idx] = p ; return r ; }
public long [] rev(long [] a) { long [] r = new long[a.length] ; int idx = a.length ; for(long p : a) r[--idx] = p ; return r ; }
public int gcd(int a, int b) { return b == 0 ? a: gcd(b, a % b); }
public int lcm(int a, int b) { return a / gcd(a, b) * b; }
public long gcd(long a, long b) { return b == 0 ? a: gcd(b, a % b); }
public long lcm(long a, long b) { return a / gcd(a, b) * b; }
public int gcd(int ... a) { int gcd = 0 ; for(int p : a) gcd = gcd(gcd , p) ; return gcd ; }
public long gcd(long ... a) { long gcd = 0L ; for(long p : a) gcd = gcd(gcd , p) ; return gcd ; }
public int lcm(int ... a) { int lcm = 1 ; for(int p : a) lcm = lcm(lcm , p) ; return lcm ; }
public long lcm(long ... a) { long lcm = 1 ; for(long p : a) lcm = lcm(lcm , p) ; return lcm ; }
public char upper(char c) { return (char)('A' + (c - 'a')); }
public char lower(char c) { return (char)('a' + (c - 'A')); }
public String yn(boolean a) { return a ? yes : no ; }
public String rev(String a) { return new StringBuilder(a).reverse().toString(); }
public void fill(int [] a , int v) { Arrays.fill(a , v); }
public void fill(long [] a , long v) { Arrays.fill(a , v); }
public void fill(int [][] a , int v) { for(int [] aa : a) fill(aa , v) ; }
public void fill(long [][] a , long v) { for(long [] aa : a) fill(aa , v) ; }
public void fill(int [][][] a , int v) { for(int [][] aa : a) fill(aa , v); }
public void fill(long [][][] a , long v) { for(long [][] aa : a) fill(aa , v); }
public int [] copy(int [] a) { return Arrays.copyOf(a , a.length); }
public long [] copy(long [] a) { return Arrays.copyOf(a , a.length); }
public String bin(int a , int len) { String b = Integer.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; }
public void debug(int [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(long [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(double [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(String [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(char [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(boolean [] a) { char [] c = conv(a); debug(c); fl();}
public void debug(int [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(long [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(double [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(String [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(char [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(boolean [][] a) { char [][] c = new char [a.length][a[0].length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = conv(a[i]) ; debug(c); fl();}
private char [] conv(boolean [] a) { char [] c = new char[a.length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = a[i] ? 'O' : 'X' ; return c ; }
private void fl() { out.flush(); }
PrintWriter out = new PrintWriter(System.out);
In in = new In();
static final long MOD7 = 1000000007;
static final long MOD9 = 998244353;
static final int inf = (1 << 30);
static final long lnf = (1L << 60);
final String yes = "Yes";
final String no = "No" ;
final char [] dir = {'U','R','D','L'};
final int [] dy4 = {-1,0,1,0};
final int [] dx4 = {0,1,0,-1};
final int [] dy8 = {-1,-1,-1,0,1,1,1,0};
final int [] dx8 = {-1,0,1,1,1,0,-1,-1};
}
class mint {
private long value;
private final long MOD;
mint(long value, long MOD)
{
this.MOD = MOD;
this.value = (value % MOD + MOD) % MOD;
}
public mint add(mint other)
{
return new mint((this.value + other.value) % MOD, MOD);
}
public mint subtract(mint other)
{
return new mint((this.value - other.value + MOD) % MOD, MOD);
}
public mint multiply(mint other)
{
return new mint((this.value * other.value) % MOD, MOD);
}
public mint inverse()
{
return new mint(pow(this.value, MOD - 2), MOD);
}
public mint divide(mint other)
{
return this.multiply(other.inverse());
}
private long pow(long a, long b)
{
long res = 1;
while (b > 0)
{
if ((b & 1) != 0) res = (res * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
public long getVal()
{
return value;
}
@Override
public String toString()
{
return String.valueOf(value);
}
}
class In
{
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}else{
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++]; else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private boolean hasNext() {
while(hasNextByte() && !isPrintableChar(buffer[ptr])) {
ptr++;
}
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while(isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while(true){
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
}else if(b == -1 || !isPrintableChar(b)){
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public char nextChar() {
return next().charAt(0);
}
public int [] IntArray(int n) {
final int [] Array = new int [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = nextInt();
}
return Array;
}
public int [][] IntArray(int n , int m) {
final int [][] Array = new int [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = IntArray(m);
}
return Array;
}
public long [] LongArray(int n) {
final long [] Array = new long [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = nextLong();
}
return Array;
}
public long [][] LongArray(int n , int m) {
final long [][] Array = new long [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = LongArray(m);
}
return Array;
}
public String [] StringArray(int n) {
final String [] Array = new String [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next();
}
return Array;
}
public char [] CharArray(int n) {
final char [] Array = new char[n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next().charAt(0);
}
return Array;
}
public char [][] CharArray(int n , int m) {
final char [][] Array = new char [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next().toCharArray();
}
return Array;
}
public char [][] CharArray2(int n , int m) {
final char [][] Array = new char [n][m];
for(int i = 0 ; i < n ; i ++ ) {
for(int j = 0 ; j < m ; j ++ ) {
Array[i][j] = next().charAt(0);
}
}
return Array;
}
public List<Integer> [] Graph(int n) {
@SuppressWarnings("unchecked")
List<Integer> [] G = new ArrayList[n];
for(int i = 0 ; i < n ; i ++ ) {
G[i] = new ArrayList<>();
}
return G ;
}
}