Pizza Delivery

题目链接：Pizza Delivery

---

提前预处理1到所有点的最短路和所有点到2的最短路。

首先对于一条边，如果反转之后变小，直接判断即可。

如果不变小，那么如果不存在与最短路上面，不变。

如果存在于最短路上面，我们把单向边看成双向，并且这个边是桥，那么变大。否则不变。

---

Ac代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=N*2;
int n,m,brige[N],a[N],b[N],c[N],dfn[N],low[N],cnt;
vector<pair<int,int> > g[N];
struct graph{
	int d[N],vis[N];
	int head[N],nex[M],to[M],w[M],tot;
	inline void add(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;}
	void Dijkstra(int s){
		priority_queue<pair<int,int> > q;	q.push({0,s});	memset(d,0x3f,sizeof d); d[s]=0;
		while(q.size()){
			int u=q.top().second;	q.pop();
			if(vis[u])	continue;	vis[u]=0;
			for(int i=head[u];i;i=nex[i])	if(d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];	q.push({-d[to[i]],to[i]});
			}
		}
	}
}g1,g2;
void Tarjan(int x,int fa){
	low[x]=dfn[x]=++cnt;
	for(auto to:g[x]){
		if(to.first==fa)	continue;	
		if(!dfn[to.first]){
			Tarjan(to.first,x);
			low[x]=min(low[x],low[to.first]);
			if(low[to.first]>dfn[x])	brige[to.second]=1;
		}else if(x!=fa) low[x]=min(low[x],dfn[to.first]);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		scanf("%lld %lld %lld",&a[i],&b[i],&c[i]),g1.add(a[i],b[i],c[i]),g2.add(b[i],a[i],c[i]);
	g1.Dijkstra(1),g2.Dijkstra(2);
	for(int i=1;i<=m;i++)	if(g1.d[a[i]]+c[i]+g2.d[b[i]]==g1.d[2])	
		g[a[i]].push_back({b[i],i}),g[b[i]].push_back({a[i],i});
	for(int i=1;i<=n;i++)	if(!dfn[i])	Tarjan(i,i);
	for(int i=1;i<=m;i++){
		if(g1.d[b[i]]+c[i]+g2.d[a[i]]<g1.d[2])	puts("HAPPY");
		else if(brige[i])	puts("SAD");
		else puts("SOSO");
	}
	return 0;
}