2020-11-29 19:11:02

# $First$ : 建图

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$ :最短路求解

### 局部代码

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$:收尾

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;
}
• star
首页