qdu-小明的贪心题(最短路+最短路的数量 )

Description

小明来到青岛上学已经一年了，他给青岛这座城市画了一张地图。在这个地图上有n个点，小明的起始点为1号点，终点为n号点，并且地图上的所有边都是单向的。小明知道从i号点到j号点的时间花费为w分钟，那么问题来了，求从1号点到n号的最小时间花费是多少？这个最少花费的路径有多少条？

Input

输入格式：输入文件第一行为两个空格隔开的数n，m，表示这张地图里有多少个点及有多少边的信息。下面m行，每行三个数I、J、w，表示从I点到J点有道路相连且花费为w.（注意，数据提供的边信息可能会重复，不过保证I<>J,1<=I,J<=n）。1<=N<=2100,0<=m<=N*(N-1), 1<=w<=2100.

Output

输出格式：输出文件包含两个数，分别是最少花费和花费最少的路径的总数.两个不同的最短路方案要求：路径长度相同（均为最短路长度）且至少有一条边不重合。若城市N无法到达则只输出一个(‘No answer’);

Sample Input 1

Sample Output 1

4 2

Sample Input 2

100 1

1 2 1

Sample Output 2

No answer

最短路+暴力找路径条数
代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<cmath>

const int maxn=1e5+;

typedef long long ll;

const ll Inf=0x3f3f3f3f3f3f3f;

using namespace std;

struct node

{

    int to;

    ll w;

};

ll map[][];

vector<node>vec[];

int vis1[][];

int vis[];

ll dis[];

int n,m;

void Init ()

{

    for(int t=;t<=n;t++)

    {

        for(int j=;j<=n;j++)

        {

            map[t][j]=Inf;

        }

    }

    for(int i=;i<=n;i++)

    {

        map[i][i]=;

    }

}

void Getmap()

{

    int u,v;

    ll w;

    for(int t=;t<=m;t++)

    {

          scanf("%d%d%lld",&u,&v,&w);

          if(map[u][v]>w)

        map[u][v]=w;

        if(vis1[u][v]!=w)

        {

            node s;

            s.to=v;

            s.w=w;

            vec[u].push_back(s);

        }

        vis1[u][v]=w;

    }

}

void Dijkstra(int u)

{

    memset(vis,,sizeof(vis));

    for(int t=;t<=n;t++)

    {

        dis[t]=map[u][t];

    }

    vis[u]=;

    for(int t=;t<n;t++)

    {

        ll minn=Inf,temp;

        for(int i=;i<=n;i++)

        {

            if(!vis[i]&&dis[i]<minn)

            {

                minn=dis[i];

                temp=i;

            }

        }

        vis[temp]=;

        for(int i=;i<=n;i++)

        {

            if(map[temp][i]+dis[temp]<dis[i])

            {

                dis[i]=map[temp][i]+dis[temp];

            }

        }

    }

}

ll bfs()

{

    ll sss=;

    queue<node>q;

    for(int t=;t<vec[].size();t++)

    {

      node nn=vec[][t];

      if(nn.w<=dis[n])

      q.push(vec[][t]);

    }

    while(!q.empty())

    {

        node now=q.front();

        q.pop();

        if(now.to==n)

        {

            if(now.w==dis[n])

            {

                sss++;

            }

        }

        for(int t=;t<vec[now.to].size();t++)

        {

            node after=vec[now.to][t];

            after.to=after.to;

            after.w=now.w+after.w;

            if(after.w<=dis[n])

            q.push(after);

        }

    }

    return sss;

}

int main()

{

    scanf("%d%d",&n,&m);

    Init();

    Getmap();

    Dijkstra();

    if(dis[n]!=Inf)

    {

    ll ans=bfs();

    printf("%lld %lld\n",dis[n],ans);

    }

    else

    {

        printf("No answer\n");

    }

    return ;

}

巴特西

qdu-小明的贪心题(最短路+最短路的数量 )

最新文章

热门文章