题目描述
这一题
图的点数 1≤T≤2500,
图的边数 1≤C≤6200,
用 朴素 或者 堆优化版 dijkstra() 算法可以在规定时间内解决
算法1
朴素版 dijkstra()
时间复杂度
$O(n^2+m)$
参考文献
算法基础课
Java 代码
import java.io.*;
import java.util.*;
public class Main{
// 记录点数,边数,起点,终点
static int T,C ,ts,te;
static int N=2510;
static int M=6300;
static int INF=0x3f3f3f3f;
//从起点到 该点的最短距离
static int[]dist= new int[N];
//该点的最短距离是否已经确定
static boolean st[]=new boolean[N];
// 存图
static int [][]g=new int[N][N];
public static void dijkstra(){
Arrays.fill(dist,INF);
dist[ts]=0;
for(int i=0;i<T;i++){
int t=-1;
// 找到距离未确定的点的集合中 距离最小的点
for(int j=1;j<=T;j++){
if(!st[j]&&(t==-1||dist[j]<dist[t])){
t=j;
}
}
st[t]=true;
// 用找到的这个点 去更新其他点的距离
for(int j=1;j<=T;j++){
dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
}
}
System.out.println(dist[te]);
}
public static void main(String[] args)throws IOException{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String[] strs=reader.readLine().split(" ");
T=Integer.parseInt(strs[0]);
C=Integer.parseInt(strs[1]);
ts=Integer.parseInt(strs[2]);
te=Integer.parseInt(strs[3]);
for(int i=1;i<=T;i++){
for(int j=1;j<=T;j++ ){
if(i==j){
g[i][j]=0;
}else{
g[i][j]=INF;
}
}
}
int rs,re,c;
for(int i=0;i<C;i++){
strs=reader.readLine().split(" ");
rs=Integer.parseInt(strs[0]);
re=Integer.parseInt(strs[1]);
c=Integer.parseInt(strs[2]);
// 双向道路
g[rs][re]=c;
g[re][rs]=c;
}
dijkstra();
reader.close();
}
}
算法2
堆优化版 dijkstra()
时间复杂度
$O(mlog(n))$
参考文献
算法基础课
Java 代码
import java.io.*;
import java.util.*;
public class Main{
static int t,c ,ts,te;
static int N=2510;
static int M=6210<<1;
static int INF=0x3f3f3f3f;
// 存图
static int[]h=new int[N];
static int[]e=new int[M];
static int[]w=new int[M];
static int[]ne=new int[M];
static int idx;
static int[]dist=new int[N];
static boolean[] st=new boolean[N];
public static void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
public static void dijkstra(){
Arrays.fill(dist,INF);
dist[ts]=0;
// 优先队列,小根堆
PriorityQueue<PII> queue=new PriorityQueue<>((a,b)-> a.first-b.first);
queue.add(new PII(0,ts));
while(queue.size()>0){
PII p=queue.poll();
int dis=p.first;
int s=p.second;
if(st[s]) continue;
st[s]=true;
// 是用堆顶的元素去更新与其相邻的点的距离
for(int i=h[s];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dis+w[i]){
dist[j]=dis+w[i];
queue.offer(new PII(dist[j],j));
}
}
}
}
public static void main(String[]args) throws IOException{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String[]strs=reader.readLine().split(" ");
t=Integer.parseInt(strs[0]);
c=Integer.parseInt(strs[1]);
ts=Integer.parseInt(strs[2]);
te=Integer.parseInt(strs[3]);
Arrays.fill(h,-1);
int x,y,z;
for(int i=0;i<c;i++){
strs=reader.readLine().split(" ");
x=Integer.parseInt(strs[0]);
y=Integer.parseInt(strs[1]);
z=Integer.parseInt(strs[2]);
add(x,y,z);
add(y,x,z);
}
dijkstra();
System.out.println(dist[te]);
reader.close();
}
}
class PII{
// 距离,编号
public int first;
public int second;
public PII(int f,int s){
first=f;
second=s;
}
}