洛谷 2299 Mzc和体委的争夺战

题目背景

ｍｚｃ与ｄｊｎ第四弹。

题目描述

ｍｚｃ家很有钱（开玩笑），他家有ｎ个男家丁（做过前三弹的都知道）。但如此之多的男家丁吸引来了我们的体委（矮胖小伙），他要来与ｍｚｃ争夺男家丁。

ｍｚｃ很生气，决定与其决斗，但ｃａｔ的体力确实有些不稳定，所以他需要你来帮他计算一下最短需要的时间。

输入输出格式

输入格式：

第一行有两个数ｎ，ｍ，ｎ表示有ｎ个停留站，ｍ表示共有ｍ条路。

之后ｍ行，每行三个数ａ［ｉ］，ｂ［ｉ］，ｃ［ｉ］，表示第ａ［ｉ］个停留站到第ｂ［ｉ］个停留站需要ｃ［ｉ］的时间。（无向）

输出格式：

一行，输出１到ｍ最短时间。

输入输出样例

输入样例#1：

输出样例#1：

说明

ｎ＜＝２５００

由于mzc大大十分着急，所以他只能等待1S。

Dijkstra算法我的spfa莫名RE。。

屠龙宝刀点击就送

#include <cstring>

#include <cstdio>

bool vis[];

int n,m,tot,i,j,dis[],atlas[][];

int min(int a,int b)

{

    return a>b?b:a;

}

int main()

{

    memset(atlas,,sizeof(atlas));

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

    int u,v,l;

    while(m--)

    {

        scanf("%d%d%d",&u,&v,&l);

        atlas[u][v]=atlas[v][u]=min(atlas[u][v],l);

    }

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

    {

        dis[i]=atlas[][i];

        vis[i]=;

    }

    vis[]=;

    dis[]=;

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

    {

        int minx=0x7fffffff,v;

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

        {

            if(!vis[j]&&dis[j]<minx)

            {

                minx=dis[j];

                v=j;

            }

        }

        vis[v]=;

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

        if(dis[j]>dis[v]+atlas[j][v])

        dis[j]=dis[v]+atlas[j][v];

    }

    printf("%d",dis[n]);

    return ;

}

巴特西

洛谷 2299 Mzc和体委的争夺战

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章