直捣黄龙 天梯

https://pintia.cn/problem-sets/994805046380707840/problems/994805049455132672

思路很裸 细节很多

记录前驱 记录最短路径数量 还要加上占领城镇数和杀敌数作为第二第三关键字

#include 
using namespace std;
typedef long long ll;
const ll N=0x3f3f3f3f3f3f3f3f;
const int maxn=2e2+10;struct node
{bool friend operator < (node n1,node n2){if(n1.val1==n2.val1){if(n1.val2==n2.val2){return n1.val3n2.val1;}ll val1,val2,val3;int id;
};priority_queue  que;
map  mp1;
map  mp2;
string ss,ee;
ll mat[maxn][maxn];
ll val[maxn],sum[maxn],dis1[maxn],dis2[maxn],dis3[maxn];
int book[maxn],pre[maxn];
int n,m,s,e;void dijkstra()
{node cur,tmp;int u,v;memset(dis1,0x3f,sizeof(dis1));memset(dis2,0,sizeof(dis2));memset(dis3,0,sizeof(dis3));memset(book,0,sizeof(book));sum[s]=1,dis1[s]=0,dis2[s]=0,dis3[s]=0,pre[s]=-1;tmp.id=s,tmp.val1=0,tmp.val2=0,tmp.val3=0;que.push(tmp);while(!que.empty()){cur=que.top();que.pop();u=cur.id;if(book[u]) continue;book[u]=1;for(v=1;v<=n;v++){if(mat[u][v]!=N&&!book[v]){if(dis1[v]==dis1[u]+mat[u][v]){sum[v]+=sum[u];if(dis2[v]==dis2[u]+1){if(dis3[v]dis1[u]+mat[u][v]){sum[v]=sum[u];dis1[v]=dis1[u]+mat[u][v],dis2[v]=dis2[u]+1,dis3[v]=dis3[u]+val[v],pre[v]=u;tmp.id=v,tmp.val1=dis1[v],tmp.val2=dis2[v],tmp.val3=dis3[v];que.push(tmp);}}}}
}void safari(int cur)
{if(cur==-1) return;safari(pre[cur]);cout<";
}int main()
{string uu,vv;ll w,ans1,ans2,ans3;int i,u,v;cin>>n>>m>>ss>>ee;mp1[ss]=1,mp2[1]=ss;for(i=2;i<=n;i++){cin>>uu>>val[i];mp1[uu]=i,mp2[i]=uu;}s=mp1[ss],e=mp1[ee];memset(mat,0x3f,sizeof(mat));while(m--){cin>>uu>>vv>>w;u=mp1[uu],v=mp1[vv];mat[u][v]=min(mat[u][v],w);mat[v][u]=min(mat[v][u],w);}dijkstra();safari(pre[e]);cout<

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