# Untitled

unknown
c_cpp
a year ago
2.0 kB
2
Indexable
Never
```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define all(a) begin(a),end(a)
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
const int mod=998244353;
const int inf=INT_MAX;
const int MAXN=100005;

vector<pair<int,pii>> Edge[MAXN],revEdge[MAXN];
vector<pii> edge;
bool shortestPath[MAXN];
int d1[MAXN],d2[MAXN],L[MAXN];
priority_queue<pii> q;
queue<int> qq;

inline void find_shortPath(){
int now=2;
do{
for(auto i:revEdge[now]){
if(d1[now]==d1[i.F]+i.S.F){
now=i.F;
shortestPath[i.S.S]=true;
break;
}
}
}while(now!=1);
}

int main(){
cin.sync_with_stdio(0),cin.tie(0);
int n,m;
cin >> n >> m;
for(int i=0;i<=n;i++){
d1[i]=d2[i]=inf;
}
for(int i=0;i<m;i++){
int u,v,l;
cin >> u >> v >> l;
Edge[u].pb({v,{l,i}});
revEdge[v].pb({u,{l,i}});
edge.pb({u,v});
L[i]=l;
}

q.push({0,1});
d1[1]=0;
while(!q.empty()){
pii now=q.top();q.pop();
if(d1[now.S]<now.F) continue;

for(auto i:Edge[now.S]){
if(d1[now.S]+i.S.F<d1[i.F]){
d1[i.F]=d1[now.S]+i.S.F;
q.push({d1[i.F],i.F});
}
}
}

q.push({0,2});
d2[2]=0;
while(!q.empty()){
pii now=q.top();q.pop();
if(d2[now.S]<now.F) continue;

for(auto i:revEdge[now.S]){
if(d2[now.S]+i.S.F<d2[i.F]){
d2[i.F]=d2[now.S]+i.S.F;
q.push({d2[i.F],i.F});
}
}
}

find_shortPath();

int ori=d1[2];
for(int i=0;i<m;i++){
int len=d1[edge[i].S]+d2[edge[i].F]+L[i];
if(d1[edge[i].S]==inf || d2[edge[i].F]==inf) len=inf;
if(len<ori) cout << "HAPPY\n";
else if(len==ori || !shortestPath[i]) cout << "SOSO\n";
else{
qq.push(1);
bool can_reach=false;
while(!qq.empty()){
int now=qq.front();qq.pop();
if(now==2){
can_reach=true;
break;
}
for(auto j:Edge[now]){
if(j.S.S==i || d1[now]+j.S.F!=d1[j.F]) continue;
qq.push(j.F);
}
}
if(can_reach) cout << "SOSO\n";