题意：给n个点m条边的有向图。每次使一条边反向，问你1到2的最短路变短，变长，还是不变。
解法：遇到这种题容易想到正向求一遍最短路d1，反向再求一遍最短路d2。纪录原图上的最短路为ans，然后分开考虑各种情况。
变短的情况：d1[y[i]]+d2[x[i]]+z[i]<ans
否则就剩下不变和变长两种情况：那么如果边（x，y）是起点到终点的最短路必须边的话，就会变长，否则会不变。
接下来的问题是 怎么求最短路的必经边？
求出原图1到2最短路图（这里要和求单源点的最短路图区别开来，单源点的最短路图使起点到所有其他点的最短路的集合），求法：如果d1[x[i]]+z[i]+d2[y[i]]==ans的话边（x[i],y[i]）就在起点到终点的最短路图上。 把这个图变为无向图，用tarjan求桥。如果边（x，y）是桥的话就是必经边，否则为非必经边。
细节详见代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,LL> pii; const int N=1e5+10; LL n,m,ans; LL d1[N],d2[N],x[N],y[N],z[N]; LL cnt=1,head[N],to[N<<1],nxt[N<<1],len[N<<1]; void add_edge(LL x,LL y,LL z) { nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt; } bool vis[N]; priority_queue<pii> q; void Dijkstra(LL d[],LL s) { while (!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); d[s]=0; q.push(make_pair(0,s)); while (!q.empty()) { pii x=q.top(); q.pop(); if (vis[x.second]) continue; vis[x.second]=1; for (LL i=head[x.second];i;i=nxt[i]) { LL y=to[i]; if (d[y]>d[x.second]+len[i]) { d[y]=d[x.second]+len[i]; q.push(make_pair(-d[y],y)); } } } } int num,low[N],dfn[N],bridge[N]; void tarjan(int x,int in) { dfn[x]=low[x]=++num; for (int i=head[x];i;i=nxt[i]) { int y=to[i]; if (!dfn[y]) { tarjan(y,i); low[x]=min(low[x],low[y]); if (low[y]>dfn[x]) bridge[len[i]]=bridge[len[i^1]]=1; } else if (i!=(in^1)) low[x]=min(low[x],dfn[y]); } } void getbridge() { cnt=1; memset(head,0,sizeof(head)); for (int i=1;i<=m;i++) if (d1[x[i]]+z[i]+d2[y[i]]==ans) add_edge(x[i],y[i],i),add_edge(y[i],x[i],i); for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i,0); } int main() { cin>>n>>m; for (int i=1;i<=m;i++) scanf("%lld%lld%lld",&x[i],&y[i],&z[i]); memset(d1,0x3f,sizeof(d1)); memset(d2,0x3f,sizeof(d2)); for (int i=1;i<=m;i++) add_edge(x[i],y[i],z[i]); Dijkstra(d1,1); cnt=1; memset(head,0,sizeof(head)); for (int i=1;i<=m;i++) add_edge(y[i],x[i],z[i]); Dijkstra(d2,2); ans=d1[2]; getbridge(); for (int i=1;i<=m;i++) if (ans>d1[y[i]]+d2[x[i]]+z[i]) puts("HAPPY"); else if (bridge[i]) puts("SAD"); else puts("SOSO"); return 0; }