直捣黄龙题解

原题链接  直捣黄龙

//朴素版本
#include 
#include 
#include 
#include 
#include 
using namespace std;const int N = 205, INF = 0x3f3f3f;
int n, k, c, g[N][N], num[N];
string s, e, a, b;
unordered_map name;
unordered_map code;int d[N], cnt[N], number[N], fa[N];
int city[N];//判断经过的城市个数
bool st[N];void Dijkstra(int s)
{//要求为路径最短，经过城市最多，打倒敌人最多fill(d, d + N, INF);cnt[s] = 1;//到自己路径数为1fa[s] = -1;//自己为根节点d[s] = 0; //到自己距离为0city[s] = 0; //经过城市为0for (int i = 0; i < n; i++){int x = -1, m = INF;//找到最近的结点，扩展子网for (int y = 0; y < n; y++){if (!st[y]){if (m > d[y]){x = y;m = d[y];}}}st[x] = true;for (int y = 0; y < n; y++){if (!st[y] && g[x][y] != INF){if (d[y] > m + g[x][y]) //更新距离{d[y] = m + g[x][y]; //更新距离fa[y] = x; //更新父节点number[y] = number[x] + num[y]; //更新歼敌数量cnt[y] = cnt[x]; //只有一条路径，所以相等city[y] = city[x] + 1; //城市+1}else if (d[y] == m + g[x][y]) //距离相等更新条数{cnt[y] += cnt[x];//条数相加//判断经过的城市的多少if (city[y] < city[x] + 1){city[y] = city[x] + 1; //更新城市fa[y] = x; //更新父节点number[y] = number[x] + num[y]; //更新歼敌数量}else if (city[y] == city[x] + 1){if (number[y] < number[x] + num[y]){fa[y] = x; //更新父节点number[y] = number[x] + num[y]; //更新歼敌数量}}}}}}}void dfs(int e)
{if (fa[e] == -1){cout << code[e];}else{dfs(fa[e]);cout << code[e] << "->";}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> k >> s >> e;name[s] = 0;code[0] = s;num[0] = 0;for (int i = 1; i < n; i++){cin >> a >> c;name[a] = i;code[i] = a;num[i] = c;}memset(g, 0x3f, sizeof(g));for (int i = 1; i <= k; i++){cin >> a >> b >> c;int start = name[a], end = name[b];g[start][end] = c;g[end][start] = c;}Dijkstra(name[s]);//输出路径int end = name[e];int i = end;stack s;while (i != -1){s.push(i);i = fa[i];}while (s.size()){int t = s.top();s.pop();cout << code[t];if (s.size())cout << "->";}cout << endl << cnt[end] << " " << d[end] << " " << number[end];return 0;
}

//堆优化版本
#include 
#include 
#include 
#include 
#include 
using namespace std;typedef pair PII;
const int N = 205, INF = 0x3f3f3f;
int n, k, c, g[N][N], num[N];
string s, e, a, b;
unordered_map name;
unordered_map code;int d[N], cnt[N], number[N], fa[N];
int city[N];//判断经过的城市个数
bool st[N];void Dijkstra(int s)
{//要求为路径最短，经过城市最多，打倒敌人最多fill(d, d + N, INF);priority_queue, greater> heap; //小根堆申请heap.push({0, s});cnt[s] = 1;//到自己路径数为1fa[s] = -1;//自己为根节点d[s] = 0; //到自己距离为0city[s] = 0; //经过城市为0while (heap.size()){//找到最近的结点，扩展子网int x = heap.top().second, m = heap.top().first;heap.pop();if (st[x])continue;st[x] = true;for (int y = 0; y < n; y++){if (!st[y] && g[x][y] != INF){if (d[y] > m + g[x][y]) //更新距离{d[y] = m + g[x][y]; //更新距离fa[y] = x; //更新父节点number[y] = number[x] + num[y]; //更新歼敌数量cnt[y] = cnt[x]; //只有一条路径，所以相等city[y] = city[x] + 1; //城市+1heap.push({d[y], y});}else if (d[y] == m + g[x][y]) //距离相等更新条数{cnt[y] += cnt[x];//条数相加//判断经过的城市的多少if (city[y] < city[x] + 1){city[y] = city[x] + 1; //更新城市fa[y] = x; //更新父节点number[y] = number[x] + num[y]; //更新歼敌数量}else if (city[y] == city[x] + 1){if (number[y] < number[x] + num[y]){fa[y] = x; //更新父节点number[y] = number[x] + num[y]; //更新歼敌数量}}}}}}}void dfs(int e)
{if (fa[e] == -1){cout << code[e];}else{dfs(fa[e]);cout << "->" << code[e];}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> k >> s >> e;name[s] = 0;code[0] = s;num[0] = 0;for (int i = 1; i < n; i++){cin >> a >> c;name[a] = i;code[i] = a;num[i] = c;}memset(g, 0x3f, sizeof(g));for (int i = 1; i <= k; i++){cin >> a >> b >> c;int start = name[a], end = name[b];g[start][end] = c;g[end][start] = c;}Dijkstra(name[s]);//输出路径int end = name[e];dfs(end);cout << endl << cnt[end] << " " << d[end] << " " << number[end];return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！