[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);

}

巴特西

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

银牛排队

最新文章

热门文章