登录后才能查看试题。
算法训练 最短路
时间限制：1.0s 内存限制：256.0MB
锦囊1
锦囊2
锦囊3
问题描述
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入格式
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式
共n-1行，第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
-2
数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
易超时，但是用了StringTokenizer后果断100%,代码有些长，但是运行起来还不错350毫秒
import java.io.*;
import java.util.*;
public class 蓝桥杯最短路 {
static int n,m,MAX = 10000000;
static boolean vis[];
static int dis[];
static Queue<Integer> que;
static int u[],v[],w[],first[],next[];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
//Scanner sc = new Scanner(new InputStreamReader(System.in));
StringTokenizer tok= new StringTokenizer("");
while(!tok.hasMoreTokens()) tok=new StringTokenizer(br.readLine());
int n=Integer.parseInt(tok.nextToken());
while(!tok.hasMoreElements()) tok=new StringTokenizer(br.readLine());
int m=Integer.parseInt(tok.nextToken());
dis = new int[n+1];
vis = new boolean[n+1];
u = new int[m+1];
v = new int[m+1];
w = new int[m+1];
first = new int[n+1];
next = new int [m+1];
for(int i=1;i<=n;i++){
first[i] = -1;
dis[i] = MAX;
}
for(int i=1;i<=m;i++){
while(!tok.hasMoreElements())tok=new StringTokenizer(br.readLine());
u[i] = Integer.parseInt(tok.nextToken());
while(!tok.hasMoreElements()) tok=new StringTokenizer(br.readLine());
v[i] = Integer.parseInt(tok.nextToken());
while(!tok.hasMoreElements()) tok = new StringTokenizer(br.readLine());
w[i] = Integer.parseInt(tok.nextToken());
next[i] = first[u[i]];
first[u[i]] = i;//逆邻接表表示法，速度！
}
spfa();
for(int i=2;i<=n;i++)
System.out.println(dis[i]) ;
}
private static void spfa() {
dis[1] = 0;
que = new PriorityQueue<Integer>();
que.clear();
que.offer(1);
while(!que.isEmpty()){
int x = que.poll();
vis[x] = false;
for(int e=first[x]; e!=-1; e=next[e]){
int temp = dis[x]+w[e];
if(dis[v[e]]>temp){//松弛操作
dis[v[e]] = temp;
if(!vis[v[e]]){
que.offer(v[e]);
vis[v[e]] = true;
}
}
}
}
}
}