深圳设计网站建设,不限关键词做网站平台,如何建设一个彩票网站,电商文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴Dijkstra算法一、题目
1、原题链接 1488. 最短距离 2、题目描述 有 N 个村庄#xff0c;编号 1 到 N。 村庄之间有 M 条无向道路#xff0c;第 i 条道路连接村庄 ai 和村…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴Dijkstra算法一、题目
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 iostream
#include queue
#include cstring
#include utility
using namespace std;
typedef pairint,int PII;
const int N100010,M3*N; //N代表点数M代表边数因需要为每个起点添加一条由虚拟源点指向的边所以开成点数3倍
int dist[N]; //存储每个点到虚拟源点的最短路径
int h[N],e[M],w[M],ne[M],idx; //h[]存储每个点第一条边的idxe[]存储每条边的终点ne[]存储每条边同起点的下一条边的idxidx存储边的编号
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_queuePII,vectorPII,greaterPII heap;dist[0]0;heap.push({0,0});while(!heap.empty()){PII theap.top();heap.pop();int vert.second;if(st[ver]) continue;st[ver]true;for(int ih[ver];i!-1;ine[i]){int je[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(){cinnm;memset(h,-1,sizeof h);while(m--){int a,b,c;cinabc;add(a,b,c);add(b,a,c);}int k;cink;while(k--){int x;cinx;add(0,x,0); //添加一个虚拟源点到每个商店距离为0的有向边}dijkstra();int q;cinq;while(q--){int y;ciny;coutdist[y]endl;}return 0;
}三、知识风暴 Dijkstra算法 基本思想将一个带权有向图中的顶点分成两组一组是未确定最短路的一组是已确定最短路的。每次将未确定最短路集合中的点按照与源点的距离递增加入已确定最短路的集合中同时每次往已确定最短路集合中加入一个点后需要用这个点来更新其他点距离源点的距离。当所有点的最短路都已确定算法结束。
