PTA A_1087 All Roads Lead to Rome
传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805379664297984解：
迪杰斯特拉 + DFS（模板）
#include <iostream>
#include <climits>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 210;
int n, k;
int d;
int pw;
bool vis;
int G;
vector<int> pre;
map<string, int> s2n;
map<int, string> n2s;
void DJS(void)
{
fill(d, d + maxn, INT_MAX);
memset(vis, false, sizeof(vis));
d = 0;
for (int i = 0; i < n; i++)
{
int u= -1, min = INT_MAX;
for (int j = 0; j <= n; j++)
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;
if (G + d < d)
{
d = G + d;
pre.clear();
pre.push_back(u);
}
else if (G + d == d)
pre.push_back(u);
}
}
}
vector<int> path, temp_path;
int opt_w = -1;
int routes = 0;
void DFS(int id)
{
if (!id)
{
int happy = 0;
routes++;
for (int i = temp_path.size() - 1; i >= 0; i--)
happy += pw];
if (happy > opt_w)
{
path = temp_path;
opt_w = happy;
}
}
temp_path.push_back(id);
for (int i = 0; i < pre.size(); i++)
DFS(pre);
temp_path.pop_back();
}
int main(void)
{
// freopen("input.txt", "r", stdin);
string s;
cin >> n >> k >> s;
n2s = s;
s2n = 0;
for (int i = 1; i < n; i++)
{
cin >> s >> pw;
n2s = s;
s2n = i;
}
fill(G, G + maxn * maxn, INT_MAX);
while (k--)
{
string s1, s2;
int cost;
cin >> s1 >> s2 >> cost;
int a = s2n, b = s2n;
G = G = cost;
}
DJS();
DFS(s2n["ROM"]);
cout << routes << " " << d] << " " << opt_w << " " << opt_w / path.size() << endl;
cout << n2s;
for (int i = path.size() - 1; i >= 0; i--)
cout << "->" << n2s];
return 0;
}
页:
[1]