当前位置: 代码迷 >> 综合 >> ZOJ 3946 Highway Project(多属性边权最短路)
  详细解决方案

ZOJ 3946 Highway Project(多属性边权最短路)

热度:58   发布时间:2023-12-08 10:49:27.0

题目链接:

题意:
有n个城市编号从0–n-1,其中编号为0的城市是首都,有m条无向边,每条边有两个属性走过这条路径的time和建造这条路径的cost,求从首都出发到达其他各个城市的最少时间和最少cost?(优先时间最少)
分析;
首先需要明确在满足到达各个城市最少时间情况下若干条边的cost之和而不是到达各个城市的cost之和!
最少时间是求一次最短路,然后在求最短路的时候判断如果有多条最短路取边cost权最少的一个作为到达这个城市的cost,最终答案是各个城市的time和cost累加。(time是从源点出发到达这个城市的最少时间)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
  相关解决方案