PTA A_1030 Travel Plan
传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805464397627392解：
迪杰斯特拉 + DFS （模板）
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 510;
int n, m, c1, c2;
int G;
int cost;
int d;//存放最短路径长度
bool vis;//是否访问过
vector<int> pre;//存放顶点在最短路径中的前驱
void DJS(int s)
{
fill(d, d + n, INT_MAX);
d = 0;
for (int i = 0; i < n; i++)
{
int u = -1, min = INT_MAX;
for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
if (!vis && d < min)min = d;
if (u == -1) return;//如果剩下的顶点与源点不通，返回
vis = true;
for (int v = 0; v < n; v++)
{
if (vis || G == INT_MAX) continue;
int t = d + G;
if (t < d)
{
d = t;
pre.clear();
pre.push_back(u);
}
else if (t == d)
pre.push_back(u);
}
}
}
int opt_cost = INT_MAX;//存放最少花费
vector<int> path, temp_path;
void DFS(int v)
{
if (v == c1)//递归边界，如果遍历到起点
{
temp_path.push_back(v);
int val = 0;
for (int i = temp_path.size() - 1; i > 0; i--)
val += cost]];
if (val < opt_cost)
{
opt_cost = val;
path = temp_path;
}
temp_path.pop_back();
return;
}
temp_path.push_back(v);
for (int i = 0; i < pre.size(); i++)
DFS(pre);
temp_path.pop_back();
}
int main(void)
{
scanf("%d %d %d %d", &n, &m, &c1, &c2);
fill(G, G + maxn * maxn, INT_MAX);
while (m--)
{
int a, b, l, c;
scanf("%d %d %d %d", &a, &b, &l, &c);
G = G = l;
cost = cost = c;
}
DJS(c1);
DFS(c2);
for (int i = path.size() - 1; i >= 0; i--)
printf("%d ", path);
printf("%d %d", d, opt_cost);
return 0;
}
页:
[1]