生命不息,奋斗不止

题解 P7100 【[w3R1] 团】

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 $内的任意两点都两两相连。所以通过样例我们可以构造出来的如图:

有了这些,就可以直接通过双重循环来将图中任意两点相连。配合输入的局部代码:

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 $,所以我们就可以通过他来更新他所指向的所有边。

局部代码

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$数组输出。

for(int i = 1; i <= n; i++){
        cout << dis[i] << ' ';
}

$ Forth $:终了 · 贴代码

#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;
}