题意:给定一个n个节点m条边的图,(n,m<=2000)(这道题口是心非,就当n,m<=104吧),每条边的长度∈[0,105],求1->求1->n的最短路共有几条。如果有无数条输出-1.

分析:要求最短路的条数,首先肯定要求最短路的长度,再思考最短路的条数能否在求长度的同时求出。

考虑较为稳定的heap+dijkstra算法求最短路。分析该算法求出源点到每个节点的最短路长度的过程,不难发现,在扩展每个节点的同时,将到达这个节点的最短路条数按照以下策略添加到下一个节点中即可。

1.ways[v]=ways[u] (dist[v]==dist[u]+edge[u,v])

2.ways[v]+=ways[u] (dist[v]>dist[u]+edge[u,v])

注意到边的长度可以为0,所以如果一条长度为0的边出现在最短路上,最短路就会有无数条。所以这里可以用ways[u]=-1表示有无数条最短路。

所以上面的两个式子可以进行更改,令-1=+∞,由于+∞+x=+∞:所以特判出现-1的情况即可。如下情况ways[v]=-1:

如果 dist[v]==dist[u]+edge[u,v]

1.ways[v]=-1 (edge[u,v]==-1)

2.ways[v]=-1 (ways[u]==-1)

3.ways[v]=-1 (ways[v]==-1)

如果 dist[v]>dist[u]+edge[u,v]

1.ways[v]=-1 (edge[u,v]==-1)

2.ways[v]=-1 (ways[u]==-1)

这样就可以在O(nlogn)的时间复杂度内求解本题。

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>

#define MX 20001
#define mod 1000000009

using namespace std;

int u[MX],v[MX],w[MX],fst[MX],nxt[MX],lnum=-1,n,m;
int dist[MX],ways[MX],vis[MX];

void addeg(int nu,int nv,int nw)
{
    lnum++;
    u[lnum]=nu,v[lnum]=nv,w[lnum]=nw;
    nxt[lnum]=fst[nu],fst[nu]=lnum;
}

void input()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)scanf("%d%d%d",&a,&b,&c),addeg(a,b,c),addeg(b,a,c);
}

priority_queue<pair<int,int> > q;

void work()
{
    int nt;
    memset(dist,0x6f,sizeof(dist)),memset(vis,0,sizeof(vis)),memset(ways,0,sizeof(ways));
    dist[1]=0,ways[1]=1;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        nt=q.top().second;q.pop();
        if(vis[nt])continue;
        vis[nt]=1;
        for(int i=fst[nt];i!=-1;i=nxt[i])
        {
            if(dist[v[i]]==dist[u[i]]+w[i])
            {
                if(w[i]==0)ways[v[i]]=-1;
                else
                {
                    if(ways[u[i]]==-1||ways[v[i]]==-1)ways[v[i]]=-1;
                    else ways[v[i]]=(ways[u[i]]+ways[v[i]])%mod;
                }
            }
            else if(dist[v[i]]>dist[u[i]]+w[i])
            {
                dist[v[i]]=dist[u[i]]+w[i];
                if(w[i]==0)ways[v[i]]=-1;
                else ways[v[i]]=ways[u[i]];
                q.push(make_pair(-dist[v[i]],v[i]));
            }
        }
    }
    cout<<ways[n]<<endl;
}

int main()
{
    memset(fst,0xff,sizeof(fst));
    input(),work();
    return 0;
}
分类: 所有

2 条评论

konnyakuxzy · 2017年5月11日 7:11 下午

看起来很强啊Orz
但是神奇的事情发生了,我的spfa+记忆化搜索0ms。。。http://k-xzy.cf/?p=1232
理论上速度应该会慢一些的。。。
算法真奇妙

    boshi · 2017年5月13日 6:44 下午

    我只是说dijkstra稳定嘛

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *