本文主要是介绍Jzzhu and Cities CodeForces - 449B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
做的很迷的一道题。。
开始用Dijkstra 将公路铁路都加入图中 看每一个有铁路直达的点 能否通过除这条直达铁路之外的路径来松弛 即该点是否存在代价小于等于这条铁路的路径
WA的很离谱 一时还找不到问题的原因 留坑。。也希望路过的大佬指正。。
#更正 填坑
其实没想的那么难 先记录下每个点通过走铁路直达的最短距离(dis2) 同时记录下从首都到这一点一共多少铁路(多条铁路肯定只留一条)
然后公路铁路都建边 跑dijkstra (这里建边时要区分是公路还是铁路) 距离记为dis1
在松弛过程中先判断是公路还是铁路 如果是一条铁路(堆顶元素代表的顶点u是1 与遍历到的点v有一条铁路直达) 那就只需要看u能不能松弛v 这是为了之后松弛其他点 因为如果这条铁路不需要去掉 那他就可能松弛其他点 不能忽略他的作用
如果是一条公路 先通过 if(dis2[v]>=dis1[u]+w) flag[v]=1; 判断是否可以把1到v的铁路去掉 可以的话就把v标记一下(flag[v]=1) 然后再正常松弛
最后扫一遍所有点 如果该点有铁路 看该点的这些铁路是否都没有用 (即可以不走直达该点的任何铁路 通过其他公路和铁路得到更短距离) 都没用则去掉所有 否则只保留一条 那一条最短铁路
#include <bits/stdc++.h>
using namespace std;
#define ll long longstruct node1
{int v;ll w;int t;int next;
};struct node2
{bool friend operator < (node2 n1,node2 n2){return n1.val>n2.val;}int id;ll val;
};node1 edge[700010];
priority_queue <node2> que;
ll dis1[100010],dis2[100010];
int first[100010],book[100010],flag[100010],cnt[100010];
int n,m1,m2,num;void addedge(int u,int v,ll w,int t)
{edge[num].v=v;edge[num].w=w;edge[num].t=t;edge[num].next=first[u];first[u]=num++;return;
}void dijkstra()
{node2 cur,tem;ll w;int i,u,v,t,sum;while(!que.empty()) que.pop();memset(dis1,0x3f,sizeof(dis1));memset(book,0,sizeof(book));memset(flag,0,sizeof(flag));tem.id=1,tem.val=0;que.push(tem);dis1[1]=0;while(!que.empty()){cur=que.top();que.pop();u=cur.id;if(book[u]) continue;book[u]=1;for(i=first[u];i!=-1;i=edge[i].next){v=edge[i].v,w=edge[i].w,t=edge[i].t;if(t==0){if(dis2[v]>=dis1[u]+w) flag[v]=1;if(dis1[v]>dis1[u]+w){dis1[v]=dis1[u]+w;tem.id=v,tem.val=dis1[v];que.push(tem);}}else{if(dis1[v]>dis1[u]+w){dis1[v]=dis1[u]+w;tem.id=v,tem.val=dis1[v];que.push(tem);}}}}sum=0;for(i=1;i<=n;i++){if(flag[i]){sum+=cnt[i];}else if(cnt[i]!=0){sum+=(cnt[i]-1);}}printf("%d\n",sum);return;
}int main()
{ll w;int i,u,v;while(scanf("%d%d%d",&n,&m1,&m2)!=EOF){memset(first,-1,sizeof(first));num=0;for(i=1;i<=m1;i++){scanf("%d%d%lld",&u,&v,&w);addedge(u,v,w,0);addedge(v,u,w,0);}memset(dis2,0x3f,sizeof(dis2));memset(cnt,0,sizeof(cnt));for(i=1;i<=m2;i++){scanf("%d%lld",&v,&w);addedge(1,v,w,1);dis2[v]=min(dis2[v],w);cnt[v]++;}dijkstra();}return 0;
}
这篇关于Jzzhu and Cities CodeForces - 449B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
