Pizza Delivery

时间限制: 2 Sec  内存限制: 128 MB

题目描述

Alyssa is a college student, living in New Tsukuba City. All the streets in the city are one-way. A new social experiment starting tomorrow is on alternative traffic regulation reversing the one-way directions of street sections. Reversals will be on one single street section between two adjacent intersections for each day; the directions of all the other sections will not change,and the reversal will be canceled on the next day.

Alyssa orders a piece of pizza everyday from the same pizzeria. The pizza is delivered along the shortest route from the intersection with the pizzeria to the intersection with Alyssa’s house. 

Altering the traffic regulation may change the shortest route. Please tell Alyssa how the social experiment will affect the pizza delivery route.

 

输入

The input consists of a single test case in the following format.

n m

a1 b1 c1

.

.

.

am bm cm

The first line contains two integers, n, the number of intersections, and m, the number of street sections in New Tsukuba City (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000). The intersections are numbered 1 through n and the street sections are numbered 1 through m. 

The following m lines contain the information about the street sections, each with three integers ai, bi, and ci (1 ≤ ai ≤ n, 1 ≤ bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100 000). They mean that the street section numbered i connects two intersections with the one-way direction from ai to bi, which will be reversed on the i-th day. The street section has the length of ci. Note that there may be more than one street section connecting the same pair of intersections.

The pizzeria is on the intersection 1 and Alyssa’s house is on the  intersection 2. It is guaranteed that at least one route exists from the pizzeria to Alyssa’s before the social experiment starts. 

 

输出

The output should contain m lines. The i-th line should be

• HAPPY if the shortest route on the i-th day will become shorter,

• SOSO if the length of the shortest route on the i-th day will not change, and

• SAD if the shortest route on the i-th day will be longer or if there will be no route from the pizzeria to Alyssa’s house.

Alyssa doesn’t mind whether the delivery bike can go back to the pizzeria or not.

 

样例输入

4 51 3 53 4 64 2 72 1 182 3 12

 

样例输出

SADSADSADSOSOHAPPY

 

来源/分类

    

---

题意：有向图中，翻转某一条边，问最短路径如何变化（变长，变短，不变）。

分析：设 d（u，v）代表从u到v的最短路，s为起点，t为终点。对于任一边（from，to），若d（s，to）+d（from，t）+value（from，to）< d（s，t），则翻转该边最短路减小。再求出所有最短路径所在的图，该图是DAG，若某一条边是DAG上的桥，则翻转该边后最短路径增大，否则不变。

证明参考：

做法：求最短路径的话正反跑两遍最短路就好了，让我感觉比较难的地方是求所有最短路径的DAG以及DAG上的桥。

求所有最短路径组成的DAG：对于任一条边（from，to），若d（s，from）+d（to，t）+value（from，to）== d（s，t），则该边是DAG上的边。

求DAG上的桥：第一种方法是把DAG上的有向边全部转化为无向边，然后用tarjan算法求无向图的桥。第二种方法是先统计出S到T的方案数，则有结论：如果这条边是桥边，那么这条边两边的点x、y也是必经点，而且s到x的方案数*y到t的方案数=s到t的方案数，这个是充分必要的。

tarjan求桥：

#include
       
        #define N 200050using namespace std; typedef struct{    int from,to,value,ori;} ss; ss edg1[N],edg2[N];vector
        
         edges1[N];int now_edges1=0;vector
         
          edges2[N];int now_edges2=0; int is_bridge[N]= {
     0};long long dis1[N],dis2[N]; void spfa1(){    for(int i=0; i
          

q; q.push(1); vis[1]=1; dis1[1]=0; while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; int Size=edges1[now].size(); for(int i=0; i

dis1[now]+e.value) { dis1[e.to]=dis1[now]+e.value; if(!vis[e.to]) { q.push(e.to); vis[e.to]=1; } } } }} void spfa2(){ for(int i=0; i

q; q.push(2); vis[2]=1; dis2[2]=0; while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; int Size=edges2[now].size(); for(int i=0; i

dis2[now]+e.value) { dis2[e.to]=dis2[now]+e.value; if(!vis[e.to]) { q.push(e.to); vis[e.to]=1; } } } }} int dfn[N]= { 0},low[N]= { 0},now_clo=1; void tarjan(int x,int pre){ dfn[x]=low[x]=now_clo++; int Size=edges2[x].size(); for(int i=0; i

dfn[x]) { is_bridge[e.ori]=1; } } else { low[x]=min(low[x],dfn[e.to]); } } }} int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=1; i<=m; i++) { int u,v,w; scanf("%d %d %d",&u,&v,&w); edges1[u].push_back(now_edges1); edg1[now_edges1++]=(ss){u,v,w,i}; edges2[v].push_back(now_edges2); edg2[now_edges2++]=(ss){v,u,w,i}; } spfa1(); spfa2(); long long bestedge=dis1[2]; for(int i=0; i