最短路使用spfa
判断次短路开二维数组存储判断，注意队列存储的是pair<int , int > 第二个是对次短的标注，同时，vis(inq) , dist , num , 都要开二维
由于题目说一定存在一条路，所以一定不存在负环，可以不开cnt数组判断。
最后一定注意要判断dist[I][0]是否等于INF，如果等于，一定不能把他赋值给次短路dist[I][1] ！！！
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
#include<map>
#include<set>
using namespace std;#define INF 0x3f3f3f3f
const int maxn = 1020 ;
const int maxm = 10005;
int point , road ;
int u , v , w , st , ed ;struct Edge{int st ,ed , cost ;Edge( int temps ,int tempe , int tempc ) : st(temps) ,ed(tempe) ,cost(tempc) {}
};
vector<int> g[maxn] ;
vector<Edge> edges ;
bool vis[maxn][2] ; int d[maxn][2] , cnt[maxn][2] , num[maxn][2] ;
int n ;
void add_edge(int u , int v , int w ){Edge temp = Edge( u , v , w ) ;edges.push_back(temp) ;g[u].push_back(edges.size()-1) ;
}
typedef pair< int , int > p2 ;
/*
bool cmp ( p2 & a , p2 & b ){return d[a.first][a.second] > d[b.first][b.second] ;
}*/bool spfa(int u )
{int i , k ;memset(vis , 0 , sizeof( vis )) ;memset(cnt , 0 , sizeof( cnt )) ;memset(num , 0 , sizeof( num )) ;for( i = 0 ; i <= n ; i ++ ){d[i][0] = d[i][1] = INF ;}d[u][0] = 0 ; vis[u][0] = true ; cnt[u][0] = 1 ; num[u][0] = 1 ;queue<p2> q ; while ( ! q.empty() ) q.pop() ;q.push( make_pair( u , 0 ) ) ;while( !q.empty() ){p2 temp = q.front() ; q.pop() ;int t1 = temp.first , t2 = temp.second ;vis[t1][t2] = 0 ;for( k = 0 ; k < g[t1].size() ; k ++ ){Edge e = edges[ g[t1][k] ] ;if( d[e.ed][0] > d[t1][t2] + e.cost ){if( d[e.ed][0] < INF ) /// very important , lose it will WA , fuck .. {d[e.ed][1] = d[e.ed][0] ;num[e.ed][1] = num[e.ed][0] ;if( !vis[e.ed][1]){vis[e.ed][1] = true ;q.push( make_pair(e.ed , 1 ) ) ;}}d[e.ed][0] = d[t1][t2] + e.cost ;num[e.ed][0] = num[t1][t2] ;if( !vis[e.ed][0] ){ /// fen liuvis[e.ed][0] = true ;//if( ++ cnt[e.ed][0] > n ) return false ;q.push( make_pair(e.ed , 0 ) ) ;}}else if( d[e.ed][0] == d[t1][t2] + e.cost ){num[e.ed][0] += num[t1][t2] ;}else if( d[e.ed][1] > d[t1][t2] + e.cost ){d[e.ed][1] = d[t1][t2] + e.cost ;num[e.ed][1] = num[t1][t2] ;if( ! vis[e.ed][1] ){vis[e.ed][1] = true ;//if( ++ cnt[e.ed][1] > n ) return false ;q.push( make_pair(e.ed , 1)) ;}}else if( d[e.ed][1] == d[t1][t2] + e.cost ){num[e.ed][1] += num[t1][t2] ;}}}return true ;
}int main( ){int m , a , b , c , kase;scanf("%d" , &kase ) ;while ( kase -- ){scanf("%d %d" , &n , &m);for( int i = 1 ; i <= n ; i ++ ) g[i].clear() ;edges.clear() ; ///for( int i = 0 ; i < m ; i ++ ){scanf("%d %d %d" , &a , &b , &c ) ;add_edge(a , b , c ) ;//add_edge(b , a , c ) ;}scanf("%d %d",&a , &b) ;spfa( a ) ;//cout << d[b][0] << " " << d[b][1] << endl ;//cout << num[b][0] << " " << num[b][1] << endl ;if( d[b][1] == d[b][0] + 1 )num[b][0] += num[b][1] ;printf("%d\n" , num[b][0] ) ;}return 0 ;
}