l3直捣黄龙

本题为三元素最短路，路径为第一元素，到起始点的节点数为第二元素，过程中的敌军数量和为第三元素

本题以字符串作为节点编号，可以用map映射成数字编号节点便于操作，结果要求输出最终路径，所以需要一个记录每个节点的前驱数组

而结果路径输出是按照字符串输出，所以还需要一个反映射map便于根据数字编号节点输出字符串编号节点

​
#include 
#define endl '\n'
#define INF 0x3f3f3f3f
#define ll long long
#define Mirai ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define COUT cout << "###" << endl;
#define pb push_back
using namespace std;
typedef pair PII;
const int N=220;
struct Edge
{int v,w,num;
};
vector g[N];
map mp;//映射map
map ump;//反映射map
int a[N];//存储每个点的敌军数
int dist[N];//最短距离
bool vis[N];
int cnt[N];//最短路径条数
int d[N];//距离起点距离多少个城镇
int path[N];//前驱节点
int sum[N];
int n,m,idx;
string s,t;
void dij()
{dist[mp[s]]=0;cnt[mp[s]]=1;path[mp[s]]=mp[s];sum[mp[s]]=0;priority_queue,greater> q;q.push({dist[mp[s]],mp[s]});while(q.size()){int u=q.top().second;q.pop();if(vis[u])continue;vis[u]=true;for(auto [v,w,num]:g[u]){if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;d[v]=d[u]+1;cnt[v]=cnt[u];path[v]=u;sum[v]=sum[u]+num;q.push({dist[v],v});}else if(dist[v]==dist[u]+w){if(d[v]"<>n>>m>>s>>t;idx=0;mp[s]=++idx;//起点编号为1ump[idx]=s;for(int i=1;i<=n;i++){dist[i]=INF;}for(int i=2;i<=n;i++){string adr;int x;cin>>adr>>x;mp[adr]=++idx;ump[idx]=adr;a[idx]=x;}for(int i=0;i>u>>v>>w;g[mp[u]].push_back({mp[v],w,a[mp[v]]});g[mp[v]].push_back({mp[u],w,a[mp[u]]});}dij();Print(mp[t]);cout<

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