| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 697627 | vjudge1 | Evacuation plan (IZhO18_plan) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*;
import java.util.*;
public class main {
static int mod = 998244353;
static int mod2 = (int) 1e9 + 7;
static long[][] st;
static long[][] stt;
static long[] tit;
static int[] tout;
static int s[];
static int N = (int) 2e5 + 500;
static int a[] = new int[N];
static int t[] ;
static int ans[];
static long arr[];
static long as[];
static FastReader sc = new FastReader(System.in);
static PrintWriter out = new PrintWriter(System.out);
static int [][]check;
static int timer=2;
static int anss=0;
static long mosdo=1073741824;
static int n, m, k;
static ArrayList<Pair>[] g;
static HashSet<Integer> set = new HashSet<>();
static int[][] dist;
static boolean[] was;
static void dfs(int curr_k, int curr, int curr_cost)
{
was[curr] = true;
for (Pair p : g[curr]) {
int x = p.to, cost = p.cost;
if (was[x] || set.contains(x)) continue;
// System.out.printf("curr = %d and curr_cost = %d\n", curr, curr_cost);
dist[curr_k][x] = Math.min(dist[curr_k][x], curr_cost + cost);
dfs(curr_k, x, curr_cost + cost);
}
}
static void init() {
dist = new int[n + 1][n + 1];
for (int i = 1; i <= n; ++i) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
for (int x : set) {
was = new boolean[n + 1];
dfs(x, x, 0);
}
}
public static void solve(int s, int t) {
System.out.printf("s = %s and t = %t\n", s, t);
}
public static void main(String[] args) throws IOException {
//int tt = sc.nextInt();
int tt = 1;
Gr1zler:
for (int WTF = 0; WTF < tt; WTF++) {
n = sc.nextInt();
m = sc.nextInt();
g = new ArrayList[n + 1];
for (int i = 1; i <= n; ++i) g[i] = new ArrayList<>();
for (int i = 0; i < m; ++i) {
int u = sc.nextInt(), v = sc.nextInt(), cost = sc.nextInt();
g[u].add(new Pair(v, cost));
g[v].add(new Pair(u, cost));
}
k = sc.nextInt();
for (int i = 0; i < k; ++i) set.add(sc.nextInt());
init();
for (int kk : set)
{
// System.out.printf("kk = %d\n", kk);
for (int i = 1; i <= n; ++i)
{
// System.out.printf("i = %d and dist[kk][i] = %d\n", i, dist[kk][i]);
}
}
int q = sc.nextInt();
for (int i = 0; i < q; ++i) {
int s = sc.nextInt(), t = sc.nextInt();
solve(s, t);
}
}
out.close();
}
public static void dfs(int x)
{
}
static int checkker(int u,int ul,int ur,int l){
//System.out.println(ul+" "+ur+" "+t[u]);
if(ur<l){
return 0;
}
if(ul>=l){
return t[u];
}
int mid=(ul+ur)/2;
return Math.max(checkker(u*2,ul,mid,l),checkker(u*2+1,mid+1,ur,l));
}
static void built(int u,int l,int r,int i,int a){
if(i>r||i<l){
return;
}
if(l==r){
t[u]=a;
return ;
}
int m=(l+r)/2;
built(u*2,l,m,i,a);
built(u*2+1,m+1,r,i,a);
t[u]=Math.max(t[u*2],t[u*2+1]);
}
static long gcd(long a, long b)
{
return b==0 ? a : gcd( b, a%b);
}
static long lcm(long a, long b)
{
return (a*b)/gcd( a, b);
}
static class Pair {
public int to, cost;
public Pair(int to, int cost) {
this.to = to;
this.cost = cost;
}
}
static long modpow(long a,long n){
long res=1;
while(n!=0){
if ((n & 1) == 1){
res*=a;
res%=mod2;
n-=1;
}else{
a*=a;
a%=mod2;
n>>=1;
}
}
return res;
}
static void arraySort(int arr[]) {
ArrayList<Integer> a = new ArrayList<Integer>();
for (int i = 0; i < arr.length; i++) {
a.add(arr[i]);
}
Collections.sort(a);
for (int i = 0; i < arr.length; i++) {
arr[i] = a.get(i);
}
}
static class FastReader {
byte[] buf = new byte[2048];
int index, total;
InputStream in;
FastReader(InputStream is) {
in = is;
}
int scan() throws IOException {
if (index >= total) {
index = 0;
total = in.read(buf);
if (total <= 0) {
return -1;
}
}
return buf[index++];
}
String next() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c > 32; c = scan()) {
sb.append((char) c);
}
return sb.toString();
}
int nextInt() throws IOException {
int c, val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
long nextLong() throws IOException {
int c;
long val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
int[] nextArrInt(int n) throws IOException {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
long[] nextArrLong(int n) throws IOException {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
}
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException {
din = new DataInputStream(
new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException {
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n') {
if (cnt != 0) {
break;
} else {
continue;
}
}
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ') {
c = read();
}
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0,
BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din == null)
return;
din.close();
}
public void printarray(int arr[]) {
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
}