Skip to content

Instantly share code, notes, and snippets.

@phonism
Created October 5, 2013 11:05
Show Gist options
  • Save phonism/6839554 to your computer and use it in GitHub Desktop.
Save phonism/6839554 to your computer and use it in GitHub Desktop.
LightOJ 1019 - Brush (V) http://lightoj.com/volume_showproblem.php?problem=1019 最短路
import java.io.BufferedReader;
import java.io.IOError;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1019 {
class Edge {
int v;
int w;
Edge next;
Edge(int v, int w, Edge next) {
this.v = v;
this.w = w;
this.next = next;
}
}
public void run() {
Scanner cin = new Scanner(System.in);
PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
int test = cin.nextInt();
for (int cas = 1; cas <= test; cas++) {
cout.print("Case " + cas + ": ");
int n = cin.nextInt();
int m = cin.nextInt();
Edge[] graph = new Edge[n + 1];
int[] dis = new int[n + 1];
for (int i = 0; i < m; i++) {
int u = cin.nextInt();
int v = cin.nextInt();
int w = cin.nextInt();
graph[u] = new Edge(v, w, graph[u]);
graph[v] = new Edge(u, w, graph[v]);
}
ArrayDeque<Integer> que = new ArrayDeque<Integer>(n);
boolean[] inque = new boolean[n + 1];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[1] = 0;
que.add(1);
inque[1] = true;
while (!que.isEmpty()) {
int u = que.poll();
inque[u] = false;
for (Edge it = graph[u]; it != null; it = it.next) {
if (dis[it.v] > dis[u] + it.w) {
dis[it.v] = dis[u] + it.w;
if (!inque[it.v]) {
que.add(it.v);
inque[it.v] = true;
}
}
}
}
if (dis[n] < Integer.MAX_VALUE) {
cout.println(dis[n]);
} else {
cout.println("Impossible");
}
}
cout.flush();
}
public static void main(String args[]) {
new P1019().run();
}
class Scanner {
BufferedReader br;
StringTokenizer st;
Scanner(InputStream in) {
br = new BufferedReader(new InputStreamReader(in));
eat("");
}
void eat(String s) {
st = new StringTokenizer(s);
}
String nextLine() {
try {
return br.readLine();
} catch (IOException e) {
throw new IOError(e);
}
}
boolean hasNext() {
while (!st.hasMoreTokens()) {
String s = nextLine();
if (s == null)
return false;
eat(s);
}
return true;
}
String next() {
hasNext();
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment