题解 P7100 【[w3R1] 团】
Chinshyo
2020-11-29 19:11:02
**单源最短路的问题**
# $ First $ : 建图
建图的过程题目告诉我们，对于每一个$ i,j $，如果$(T_i,W_i),(T_j,W_i)∈S$，那么$ T_i,T_j $之间就会有权值为$ W_i+W_j $的无向边。那么根据题意我们可以知道，**只要在集合$ S $内的任意两点都两两相连**。所以通过样例我们可以构造出来的如图：
有了这些，就可以直接通过双重循环来将图中任意两点相连。配合输入的局部代码：
```cpp
int n, k;
cin >> n >> k;
int t, a, b;
for(int i = 1; i <= k; i++) {
cin >> t;
vector < pair<int, int> > Set;
for(int j = 1; j <= t; j++){
cin >> a >> b;
Set.push_back(make_pair(a, b));
}
for(int j = 0; j < t; j++){
for(int k = j + 1; k < t; k++){
graph[Set[j].first].push_back((node){Set[k].first, Set[k].second + Set[j].second});
graph[Set[k].first].push_back((node){Set[j].first, Set[k].second + Set[j].second});
}
}
}
```
# $ Second $ :最短路求解
我们所知的最流行的两种最短路求解算法就是$ Dijkstra $了。
### 算法简介
在最开始时，只有起点的最短距离是确定的。在尚未使用过的顶点中，距离的$d[i]$最小顶点就是最短路径已经确定的顶点。因为本题不存在负边，所以不会再之后的更新中变小。**他的局限就是无法考虑负权**。
如图，箭头所指节点的最短路径已知是$ 0 $，所以我们就可以通过他来更新他所指向的所有边。
### 局部代码
```cpp
while(!pr.empty()){
int now = pr.top().second;//记录节点当时的编号
pr.pop();
if(visited[now] == true){//判重
continue;
}
visited[now] = true;
for(int i = 0; i < graph[now].size(); i++){
int next = graph[now][i].to;//下一个节点
if(dis[now] + graph[now][i].cost < dis[next]){//如果找到更优解
dis[next] = dis[now] + graph[now][i].cost;//更新最短路
pr.push(make_pair(dis[next], next));//压入小根堆
}
}
}
```
# $ Third $:收尾
本题最终是要求输出到每个节点的最短距离。所以我们可以直接将整个$dis$数组输出。
```cpp
for(int i = 1; i <= n; i++){
cout << dis[i] << ' ';
}
```
# $ Forth $:终了 · 贴代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MaxN = 200005;
struct node{
int to, cost;
};
vector <node> graph[MaxN];
bool visited[MaxN];
int dis[MaxN];
int main(){
int n, k;
cin >> n >> k;
int t, a, b;
for(int i = 1; i <= k; i++) {
cin >> t;
vector < pair<int, int> > Set;
for(int j = 1; j <= t; j++){//无脑输入
cin >> a >> b;
Set.push_back(make_pair(a, b));
}
for(int j = 0; j < t; j++){
for(int k = j + 1; k < t; k++){
graph[Set[j].first].push_back((node){Set[k].first, Set[k].second + Set[j].second});
graph[Set[k].first].push_back((node){Set[j].first, Set[k].second + Set[j].second});
}
}
}
priority_queue< pair<int, int> , vector< pair<int, int> > , greater< pair<int, int> > > pr; //first->cost second->node
pr.push(make_pair(0, 1));
for(int i = 1; i <= n; i++){
dis[i] = INT_MAX;
}
dis[1] = 0;
memset(visited, false, sizeof(visited));
while(!pr.empty()){
int now = pr.top().second;//记录节点当时的编号
pr.pop();
if(visited[now] == true){//判重
continue;
}
visited[now] = true;
for(int i = 0; i < graph[now].size(); i++){
int next = graph[now][i].to;//下一个节点
if(dis[now] + graph[now][i].cost < dis[next]){//如果找到更优解
dis[next] = dis[now] + graph[now][i].cost;//更新最短路
pr.push(make_pair(dis[next], next));//压入小根堆
}
}
}
for(int i = 1; i <= n; i++){//输出
cout << dis[i] << ' ';
}
return 0;
}
```