学步园

题意：旅行团每天固定的从S地出发到达T地，为了省油要求尽量走最短路径或比最短路径长1单位距离的路径，求满足条件的路径条数

这是一次对dijstra的深刻理解 ，好吧......不会做，参考大神思路

因为有重边，所以不能使用邻接矩阵（真的不是因为存不下.....），然后为了减少代码复杂度，使用了链式前向星

struct Edge{
    int v, next, w;
}Graph[maxn*maxn];//跟大神学的，本题采用链式前向星
void add_E(int u, int v, int w){  //A is u ，B is v
    Graph[e_cnt].v=v;
    Graph[e_cnt].next=adj[u];
    Graph[e_cnt].w=w;
    adj[u]=e_cnt++;
}

上面是链式前向星的数据结构，存边，v是一条边的终点，next是上一条邻边，注意是起始点相同；需要一个adj[]数组来保存最后一条和u结点相连的边的编号，这样可以用链来访问所有的边

然后就是二维dijstra ，求出最短路和次短路，最后比较一下次短路是否比最短路多1即可；

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <limits>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Si set<int>
#define LL long long
#define pb push_back
#define PS printf(" ")
#define Vi vector<int>
#define LN printf("\n")
#define lson l,m,rt << 1
#define rson m+1,r,rt<<1|1
#define SD(a) scanf("%d",&a)
#define PD(a) printf("%d",a)
#define SET(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i(0);i<(a);i++)
#define FD(i,a) for(int i(a);i>=(1);i--)
#define FOR(i,a,b) for(int i(a);i<=(b);i++)
#define FOD(i,a,b) for(int i(a);i>=(b);i--)
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
const int maxn = 1005;
const int INF = 0x3fffffff;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const double pi = acos(-1.0);
using namespace std;

int N,M;// vertex num , edge num;
bool vis[maxn][2];// visit flag
int e_cnt,adj[maxn],dis[maxn][2],cnt[maxn][2];
struct Edge{
    int v, next, w;
}Graph[maxn*maxn];//跟大神学的，本题采用链式前向星
void add_E(int u, int v, int w){  //A is u ，B is v
    Graph[e_cnt].v=v;
    Graph[e_cnt].next=adj[u];
    Graph[e_cnt].w=w;
    adj[u]=e_cnt++;
}
void dijstra(int S,int F){

    SET(vis,false);
    SET(cnt,0);
    FOR(i,1,N) dis[i][0]=dis[i][1]=INF;
    cnt[S][0]=1;
    dis[S][0]=0;

    int k,tmp,flag;

    FF(i,2*N){
        tmp=INF;
        FOR(j,1,N){
            if(!vis[j][0] && dis[j][0]<tmp){
                tmp=dis[j][0];
                flag=0;
                k=j;
            }else if(!vis[j][1] && dis[j][1]<tmp){
                tmp=dis[j][1];
                flag=1;
                k=j;
            }
        }
        //此时 tmp 是 dis[j][0] 和 dis[j][1] 当中最短的
        if(tmp==INF) break;

        vis[k][flag]=true;
        int w,v;
        for(int j=adj[k];j;j=Graph[j].next){
            w=Graph[j].w;
            v=Graph[j].v;

            if(dis[v][0] > tmp+w ){
                //此时最短路变为次短路
                dis[v][1]=dis[v][0];
                cnt[v][1]=cnt[v][0];
                //新的最短路是tmp+w
                dis[v][0]=tmp+w;
                cnt[v][0]=cnt[k][flag];
            }else if(dis[v][0]== tmp+w){
                cnt[v][0] += cnt[k][flag];
            }else if(dis[v][1] > tmp+w){
                dis[v][1]=tmp+w;
                cnt[v][1]=cnt[k][flag];
            }else if(dis[v][1] == tmp+w){
                cnt[v][1] += cnt[k][flag];
            }
        }
    }
    int ans=cnt[F][0];
    if(dis[F][0]+1==dis[F][1]){
         ans+=cnt[F][1];
    }
    PD(ans);LN;
}
int main()
{
    int cas, S, F;
    SD(cas);
    while(cas--){
        SD(N);SD(M);
        SET(adj,-1);
        e_cnt=1;
        FOR(i,1,M){
            int A,B,L;
            SD(A);SD(B);SD(L);
            add_E(A,B,L);
        }
        SD(S);SD(F);
        dijstra(S,F);
    }
    return 0;
}