一、最短路必经边:先求出任意一条最短路,记录这条最短路上所有的边,枚举这些边:
题目描述
Farmer John 热衷于散步,每天早上他都要从 1 号仓库走到 n 号仓库。 Farmer John 家的 n 个仓库被 m 条双向道路连通起来,每条道路有一个长度 w。而Farmer John 又不喜欢走路,所以他走的是从 1 号仓库到 n 号仓库的最短路。
但是 Farmer 的奶牛们总想搞点事情,他们计划着把 m 条道路的其中一条变成原来长度的 2 倍,使得 Farmer John 可能会多走一点路。
他们想知道,最多能让 Farmer John 多走多少路呢?

输入
第一行一个正整数 n,m,表示仓库个数和道路条数。
接下来 m 行,每行三个正整数,表示每条双向道路的连接的仓库和该双向道路的长度。

输出
输出只有一行,表示最多能让 Farmer John 每天早上多走多少路。

样例输入
复制样例数据
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
样例输出
2

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=1000000007;
const int maxn=50100;
const int maxx=300;
const int inf=0x3f3f3f3f;
int head[maxx],edge[maxn],ver[maxn],nt[maxn];
int d[maxx];
int ha[maxx];
int pre[maxx];
int tot=1,n,m;
bool flag=false;

void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

int Dij(void)
{
    memset(d,0x3f,sizeof(d));
    memset(ha,0,sizeof(ha));
    d[1]=0;
    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,1));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ha[x]=true;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                if(!flag)
                    pre[y]=i;
                q.push(make_pair(-d[y],y));
            }
        }
    }
    return d[n];
}


int main(void)
{
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    int cnt=Dij();
    flag=true;
    int _max=0;
    for(int i=2;i<=n;i++)
    {
        int k=pre[i];
        edge[k]=edge[k]*2,edge[k^1]=edge[k^1]*2;
        _max=max(_max,Dij());
        edge[k]=edge[k]/2,edge[k^1]=edge[k^1]/2;
    }
    printf("%d\n",_max-cnt);
    return 0;
}

二、生成树计数,不同于最短路计数:
在顺利攻破Lord lsp的防线之后,lqr一行人来到了Lord lsp的城堡下方。

Lord lsp黑化之后虽然拥有了强大的超能力,能够用意念力制造建筑物,但是智商水平却没怎么增加。

现在lqr已经搞清楚黑暗城堡有N个房间,M条可以制造的双向通道,以及每条通道的长度。

lqr深知Lord lsp的想法,为了避免每次都要琢磨两个房间之间的最短路径,Lord lsp一定会把城堡修建成树形的。

但是,为了尽量提高自己的移动效率,Lord lsp一定会使得城堡满足下面的条件:

设 D[i] 为如果所有的通道都被修建,第 i 号房间与第1号房间的最短路径长度;而 S[i] 为实际修建的树形城堡中第 i 号房间与第1号房间的路径长度;要求对于所有整数 i,有 S[i]=D[i] 成立。

为了打败Lord lsp,lqr想知道有多少种不同的城堡修建方案。

你需要输出答案对 231–1 取模之后的结果。

输入格式
第一行有两个整数 N 和 M。

之后 M 行,每行三个整数X,Y 和L,表示可以修建 X 和 Y 之间的一条长度为 L 的通道。

输出格式
一个整数,表示答案对 231–1 取模之后的结果。

数据范围
2≤N≤1000,
N−1≤M≤N(N−1)/2 ,
1≤L≤100
输入样例:
3 3
1 2 2
1 3 1
2 3 1
输出样例:
2

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=(1ll<<31)-1;
const int maxn=1000100;
const int maxx=1200;
const int inf=0x3f3f3f3f;
int head[maxx],edge[maxn],ver[maxn],nt[maxn];
int d[maxx];
int ha[maxx];
int cnt[maxx];
int tot=1,n,m;


void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

void Dij(void)
{
    memset(d,0x3f,sizeof(d));
    memset(ha,0,sizeof(ha));
    d[1]=0;
    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,1));

    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ha[x]=true;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                cnt[y]=1;
                q.push(make_pair(-d[y],y));
            }
            else if(d[y]==d[x]+z)
            {
                cnt[y]++;
            }
        }
    }
    return ;
}


int main(void)
{
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    Dij();
    cnt[1]=1;
    ll ans=1;
    for(int i=1;i<=n;i++)
    {
        ans=ans*cnt[i]%mod;
    }
    printf("%lld\n",ans);
    return 0;
}