[USACO07FEB]银牛派对Silver Cow Party---最短路模板题

银牛排队

---

对于我这种蒟蒻来说，还是不要跑一次单元最短路。跑两次好写呀(～￣▽￣)～

而题目中是有向图。如果如果按照题意进行最短路的话。就会出现一个单终点最短路和一个单起点最短路

对于单起点自然就是套模板，但对于单终点最短路怎么办呢？

显而易见的是，只有一个终点废话呢你(/ﾟДﾟ)/

这样我们就可以反向存一次有向边。将终点变为起点，这样的话就可以套模板了合着就是刷模板题呀(▼⊿▼)

#include<iostream> #include<cstdio> #include<queue> using namespace std; int head[1001][2]; struct node {int point;int next;int dist; }; node line[101000][2]; int tail; queue<int>q0; queue<int>q1; bool exist[1001][2]; int dis[1001][2]; void add(int x,int y,int val,int d) {line[++tail][d].point=y;line[tail][d].dist=val;line[tail][d].next=head[x][d];head[x][d]=tail; } int main() {int n,m,begin;scanf("%d%d%d",&n,&m,&begin);for(int i=1;i<=n;i++){head[i][0]=head[i][1]=-1;dis[i][0]=dis[i][1]=0x7fffffff;}int a,b,c;for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);add(a,b,c,0);add(b,a,c,1);}int pass;q0.push(begin);dis[begin][0]=0;exist[begin][0]=true;while(!q0.empty()){pass=q0.front();q0.pop();exist[pass][0]=false;int need=head[pass][0];while(need!=-1){if(dis[line[need][0].point][0]>dis[pass][0]+line[need][0].dist){dis[line[need][0].point][0]=dis[pass][0]+line[need][0].dist;if(!exist[line[need][0].point][0])q0.push(line[need][0].point);}need=line[need][0].next;}}q1.push(begin);exist[begin][1]=true;dis[begin][1]=0;while(!q1.empty()){pass=q1.front();q1.pop();exist[pass][1]=false;int need=head[pass][1];while(need!=-1){if(dis[line[need][1].point][1]>dis[pass][1]+line[need][1].dist){dis[line[need][1].point][1]=dis[pass][1]+line[need][1].dist;if(!exist[line[need][1].point][1])q1.push(line[need][1].point);}need=line[need][1].next;}}int ans=-0x7fffff;for(int i=1;i<=n;i++)if(i!=begin)ans=max(ans,dis[i][0]+dis[i][1]);printf("%d",ans); }

转载于:https://www.cnblogs.com/Lance1ot/p/8509910.html

超强干货来袭 云风专访：近40年码龄，通宵达旦的技术人生

总结

以上是生活随笔为你收集整理的[USACO07FEB]银牛派对Silver Cow Party---最短路模板题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。