BZOJ 2200 道路与航线

题目大意

有两种路，一种没负数，一种没环，求单源最短路。

solution

存在负边权Dij一定不能用嘛，显然不是

根据题意能看出来是tarjan，将双向边缩点，得到的是一个DAG，然后刚刚学的topsort拿来试试，好像可以码过

然鹅这道题还有一个神奇的方法——双端队列优化的Spfa。就是说，在把点入队的时候把目前的距离和队首元素比较一下，如果比队首元素大就推到队尾，否则放在队首，这样的话就可以尽量减少之后的点入队的次数从而达到优化效果。

瞅瞅LZZ的blog，看来我千年的inline还有用……

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<iostream>

#include<string>

#include<queue>

using namespace std;

const int maxn=25000+3,maxe=150000+3,inf=1000000000;

int t,r,p,s,tot,head[maxn],dis[maxn],to[maxe],w[maxe],next[maxe];

bool vis[maxn];

deque<int> q;

inline void add(int a,int b,int l){

	w[++tot]=l;

	to[tot]=b;

	next[tot]=head[a];

	head[a]=tot;

}

inline void Spfa(int begin){

	for(int i=1;i<=t;i++) dis[i]=inf;

	dis[begin]=0,vis[begin]=1;

	q.push_back(begin);

	while(!q.empty()){

		int u=q.front();

		q.pop_front();

		vis[u]=0;

		for(int i=head[u];i;i=next[i]){

			int v=to[i];

			if(dis[v]>dis[u]+w[i]){

				dis[v]=dis[u]+w[i];

				if(!vis[v]){

					if(!q.empty()&&dis[v]>=dis[q.front()]) q.push_back(v);

                    else q.push_front(v);

					vis[v]=1;

				}

			}

		}

	}

}

int main(){

	tot=1;

	scanf("%d%d%d%d",&t,&r,&p,&s);

	int x,y,w;

	for(int i=1;i<=r;i++){

		scanf("%d%d%d",&x,&y,&w);

		add(x,y,w);

		add(y,x,w);

	}

	for(int i=1;i<=p;i++){

		scanf("%d%d%d",&x,&y,&w);

		add(x,y,w);

	}

	Spfa(s);

	for(int i=1;i<=t;i++){

		if(dis[i]==inf) printf("NO PATH\n");

		else printf("%d\n",dis[i]);

	}

	return 0;

}

BZOJ 2200 道路与航线（图论）的相关教程结束。