`
java-mans
  • 浏览: 11710450 次
文章分类
社区版块
存档分类
最新评论

HDU 3986 最短路+枚举

 
阅读更多

这题HDU 1595 find the longest of the shortest 就是一模一样的

但是出现了重边,就比较恶心人了

然后就将输入的数据先排序,然后出现重边的肯定在一块,然后对每条边存储的是它最短的情况和次短的情况即可

/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 100000000
#define MAXN 1005
#define PI acos(-1.0)
using namespace std;
struct node
{
    int v, next;
    int w, worst;
    void init(){worst = INF; }
}edge[MAXN * MAXN];
int vis[MAXN], pre[MAXN], head[MAXN], d[MAXN];
int q[MAXN * MAXN];
int n, m, e;
struct wwj
{
    int u, v, w;
}in[MAXN * 100];
int uu[MAXN * 100], vv[MAXN * 100];
bool cmp(wwj x, wwj y)
{
    if(x.u == y.u && x.v == y.v) return x.w < y.w;
    else if(x.u == y.u) return x.v < y.v;
    else return x.u < y.u;
}
void insert(int x, int y, int w)
{
    int flag = 0;
    for(int i = head[x]; i != -1; i = edge[i].next)
    {
        if(edge[i].v == y)
        {
            if(edge[i].worst == INF && edge[i].w != INF) edge[i].worst = w;
            flag = 1;
            break;
        }
    }
    if(!flag)
    {
        edge[e].v = y;
        edge[e].w = w;
        edge[e].next = head[x];
        head[x] = e++;
    }
}
void spfa(int src)
{
    for(int i = 1; i <= n; i++)
        d[i] = INF;
    int h = 0, t = 1;
    memset(vis, 0, sizeof(vis));
    d[src] = 0;
    q[0] = src;
    vis[src] = 1;
    while(h < t)
    {
        int u = q[h++];
        vis[u] = 0;
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if(d[v] > d[u] + w)
            {
                pre[v] = u;
                d[v] = d[u] + w;
                if(!vis[v])
                {
                    q[t++] = v;
                    vis[v] = 1;
                }
            }
        }
    }
}

void init()
{
    e = 0;
    memset(head, -1, sizeof(head));
    for(int i = 0; i < 5 * m; i++) edge[i].init();
}
void bechange(int u, int v)
{
    for(int i = head[u]; i != -1; i = edge[i].next)
        if(edge[i].v == v)
            swap(edge[i].w, edge[i].worst);
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        init();
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &in[i].u, &in[i].v, &in[i].w);
            in[i + m].u = in[i].v;
            in[i + m].v = in[i].u;
            in[i + m].w = in[i].w;
        }
        sort(in, in + 2 * m, cmp);
        for(int i = 0; i < 2 * m; i++)
            insert(in[i].u, in[i].v, in[i].w);
        spfa(1);
        int ans = d[n];
        int cnt = 0;
        for(int i = n; i != 1; i = pre[i])
        {
            uu[cnt] = i;
            vv[cnt] = pre[i];
            cnt++;
        }
        for(int i = 0; i < cnt; i++)
        {
            bechange(uu[i], vv[i]);
            bechange(vv[i], uu[i]);
            spfa(1);
            ans = max(ans, d[n]);
            bechange(uu[i], vv[i]);
            bechange(vv[i], uu[i]);
        }
        if(ans >= INF) puts("-1");
        else
        printf("%d\n", ans);
    }
    return 0;
}


分享到:
评论

相关推荐

    acm入门之枚举搜索

    acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs

    ACM hdu 线段树题目+源代码

    ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...

    hdu 1753 大明A+B

    Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,...请在一行里面输出输出A+B的值,请输出最简形式。

    HDU刷题地图+精选详细笔记

    本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!

    HDU+2000-2099+解题报告

    HDU(杭州电子科技大学)在线评测系统是许多编程竞赛爱好者和学习者经常访问的平台,它提供了大量的算法题目供用户练习和挑战。这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、...

    HDU+2000-2099+解题报告.zip

    1. **动态规划**:动态规划是一种用于解决最优化问题的常用方法,例如背包问题、最长公共子序列、矩阵链乘法等。解题报告会解释如何定义状态、设计状态转移方程,并给出具体代码实现。 2. **图论算法**:包括最短...

    最短路(HDU-2544).rar

    《最短路问题详解》 在计算机科学领域,最短路问题是一个经典的图论问题,其目标是寻找网络中两点间路径的最小成本。这个问题在众多应用中都有所体现,如交通规划、通信网络设计、社交网络分析等。在本篇内容中,...

    HDUc++上机测试真题(错题汇集1

    在C++编程语言中,`new`和`delete`是两个关键的操作符,它们与C语言中的`malloc`和`free`有所不同。`new`不仅分配内存,还会根据指定的类型调用对应的构造函数来初始化对象,而`malloc`仅仅分配内存,不涉及对象的...

    hdu 300+ AC 代码

    HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...

    hdu 3341(ac自动机+状态压缩)

    hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    HDU最全ac代码

    "HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码集合,旨在帮助学习者理解和掌握各种算法,提升编程解决问题的能力。 首先,我们来了解一下ACM/ICPC比赛。这是一项全球性的编程竞赛,参赛...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    "hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

Global site tag (gtag.js) - Google Analytics