写在前面
本人CSDN博客主页:这里
一、题目
1、原题链接
1488. 最短距离
2、题目描述
有 N 个村庄,编号 1 到 N。
村庄之间有 M 条无向道路,第 i 条道路连接村庄 ai 和村庄 bi ,长度是 ci。
所有村庄都是连通的。
共有 K 个村庄有商店,第 j 个有商店的村庄编号是 xj。
然后给出 Q 个询问,第 k 个询问给出一个村庄的编号 yk,问该村庄距离最近的商店有多远?
输入格式
第一行包含两个整数 N,M。
接下来 M 行,每行包含三个整数 ai,bi,ci,表示第 i 条道路连接村庄 ai 和村庄 bi,长度是 ci。
再一行包含整数 K。
接下来 K 行,每行包含一个整数 xj,表示第 j 个有商店的村庄编号是 xj。
再一行包含整数 Q。
接下来 Q 行,每行包含一个整数 yk,表示询问编号为 yk 的村庄与其距离最近的商店之间的距离。
输出格式
对于每个询问,输出该询问的结果。
数据范围
2≤N≤105,N−1≤M≤min(N(N−1)/2,105),1≤Q≤105,1≤K≤N,1≤ci≤10000
输入样例:
7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7输出样例:
3
1
3
0
0
6
0
二、解题报告
1、思路分析
思路来源:y总讲解视频
y总yyds
(1)将每个商店看做起点,在图中添加一个虚拟源点(起点),该点到其后面所有商店的距离均为0(有向边),则可以将从村庄走到商店的最短路径转化为从村庄走到源点(也就是从源点到村庄)的最短路径,两者等价。
(2)模拟上述过程,求从虚拟源点到村庄的最短路径,即为从村庄到商店的最短路径。
2、时间复杂度
时间复杂度为O(mlogn)(n表示点数,m表示边数)
3、代码详解
#include
#include
#include
#include
using namespace std;
typedef pair PII;
const int N=100010,M=3*N; //N代表点数,M代表边数,因需要为每个起点添加一条由虚拟源点指向的边,所以开成点数3倍
int dist[N]; //存储每个点到虚拟源点的最短路径
int h[N],e[M],w[M],ne[M],idx; //h[]存储每个点第一条边的idx,e[]存储每条边的终点,ne[]存储每条边同起点的下一条边的idx,idx存储边的编号
bool st[N];
int n,m;
//邻接表中添加一条边
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
//堆优化dijkstra求最短路
int dijkstra(){
memset(dist,0x3f,sizeof dist);
priority_queue,greater> heap;
dist[0]=0;
heap.push({0,0});
while(!heap.empty()){
PII t=heap.top();
heap.pop();
int ver=t.second;
if(st[ver]) continue;
st[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[ver]+w[i]){
dist[j]=dist[ver]+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -3;
else return dist[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
int k;
cin>>k;
while(k--){
int x;
cin>>x;
add(0,x,0); //添加一个虚拟源点到每个商店距离为0的有向边
}
dijkstra();
int q;
cin>>q;
while(q--){
int y;
cin>>y;
cout
三、知识风暴
Dijkstra算法
- 基本思想:将一个带权有向图中的顶点分成两组,一组是未确定最短路的,一组是已确定最短路的。每次将未确定最短路集合中的点,按照与源点的距离递增加入已确定最短路的集合中,同时每次往已确定最短路集合中加入一个点后,需要用这个点来更新其他点距离源点的距离。当所有点的最短路都已确定,算法结束。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net