当前位置: 首页 > article >正文

算法——图论——交通枢纽

原题

#include <iostream>
#include <vector>
#include <queue>


using namespace std;
typedef pair<int, int> PII;

vector<PII> graph[100];
vector<vector<int>> Dist(100, vector<int>(100, -1));
vector<bool> State(100, false);

void Dijkstra(int s, int n) {
    for (int i = 0; i < n; ++i) {
        State[i] = false;
    }

    Dist[s][s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.emplace(0, s);

    while (!pq.empty()) {
        pair<int, int> cur = pq.top();
        pq.pop();

        if (State[cur.second]) continue;
        else State[cur.second] = true;

        for (auto neighbor: graph[cur.second]) {
            if (Dist[s][neighbor.first] == -1 || Dist[s][neighbor.first] > Dist[s][cur.second] + neighbor.second) {
                Dist[s][neighbor.first] = Dist[s][cur.second] + neighbor.second;
                pq.emplace(Dist[s][neighbor.first], neighbor.first);
            }
        }
    }
}

int main() {

    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }
    int cityNum;
    vector<int> cityList;
    while (cin >> cityNum) {
        cityList.push_back(cityNum);
    }

    for (int city: cityList) {
        Dijkstra(city, n);
    }

    int sum = -1, resultCity;
    for (int i = 0; i < cityList.size(); ++i) {
        int tmp = 0;
        for (int j = 0; j < n; ++j) {
            tmp += Dist[cityList[i]][j];
        }
        if (sum == -1 || tmp < sum) {
            sum = tmp;
            resultCity = cityList[i];
        }
    }
    cout << resultCity << " " << sum << endl;
    return 0;
}


http://www.kler.cn/a/590069.html

相关文章:

  • 【Maven-plugin】有多少官方插件?
  • 在MacOS 10.15上安装Node.js
  • c++如何利用线程池和epool设计高并发服务器
  • 高效手机检测:视觉分析技术的优势
  • 【css酷炫效果】纯CSS实现3D翻转卡片动画
  • Java 大视界 -- Java 大数据在智能教育虚拟实验室建设与实验数据分析中的应用(132)
  • LeRobot源码剖析——对机器人各个动作策略的统一封装:包含ALOHA ACT、Diffusion Policy、VLA模型π0
  • 【binlog2sql实践】MySQL数据库binlog日志ROW格式转换标准SQL
  • Linux 蓝牙音频软件栈实现分析
  • 美团Leaf分布式ID生成器:使用详解与核心原理解析
  • 关于虚拟网络编辑器还原默认设置那些坑
  • Pandas DataFrame:数据分析的利器
  • 解决从deepseek接口获取的流式响应输出到前端都是undefined的问题
  • 微服务架构中10个常用的设计模式
  • 平面阵列天线波束形成的Matlab仿真
  • 一场由 ES 分片 routing 引发的问题
  • 2025年Postman的五大替代工具
  • 【软考-架构】5.3、IPv6-网络规划-网络存储-补充考点
  • SpringData Redis:RedisTemplate配置与数据操作
  • 02 windows qt配置ffmpeg开发环境搭建