首页 > 其他分享 >HDU 1595 find the longest of the shortest

HDU 1595 find the longest of the shortest

时间:2023-07-18 19:37:32浏览次数:39  
标签:HDU used idx int 路径 mark 1595 cost find


题意:对于题目给定的一个图,问去掉起点到终点的最短路径上的某一条边之后起点到终点的最短距离里的最大值。

思路:先计算原图的最短路径,保存最短路径。枚举最短路径每一条边,删掉该边,然后计算最短路径,保留最大的那个即可。

实现:先用一个spfa求得最短路径,用一个路径数组保存路径。然后枚举每一条路径上的边,用另一个spfa实现对该边的假删除(即对其进行标记,表示现在删的是此边)。然后比较得出最长的那个最短路的值,将其输出。


代码:

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

using namespace std;
#define N 1010
#define inf 0x7fffffff

bool mark[N];
bool used[N][N];
int p[N];
int d[N];
int pre[N];

struct node {
    int v,cost,next;
} e[N*N];

int idx;
int n,m;

queue<int>que;

void add(int u,int v,int c) {
    e[idx].v=v;
    e[idx].cost=c;
    e[idx].next=p[u];
    p[u]=idx++;
}

void spfa() {
    int i,j;
    int u,v;
    for(i=1; i<=n; i++) {
        mark[i]=false;
        d[i]=inf;
    }
    while(!que.empty())
        que.pop();
    mark[1]=true;
    d[1]=0;
    que.push(1);
    while(!que.empty()) {
        u=que.front();
        que.pop();
        mark[u]=false;
        for(i=p[u]; i!=-1; i=e[i].next) {
            v=e[i].v;
            if(d[v]>d[u]+e[i].cost) {
                d[v]=d[u]+e[i].cost;
                pre[v]=u;
                if(!mark[v]) {
                    mark[v]=true;
                    que.push(v);
                }
            }
        }
    }
}

int work() {
    int i,j;
    int u,v;
    for(i=1; i<=n; i++) {
        mark[i]=false;
        d[i]=inf;
    }
    while(!que.empty())
        que.pop();
    mark[1]=true;
    d[1]=0;
    que.push(1);
    while(!que.empty()) {
        u=que.front();
        que.pop();
        mark[u]=false;
        for(i=p[u]; i!=-1; i=e[i].next) {
            v=e[i].v;
            if(used[u][v]&&d[v]>d[u]+e[i].cost) {
                d[v]=d[u]+e[i].cost;
                if(!mark[v]) {
                    mark[v]=true;
                    que.push(v);
                }
            }
        }
    }
    return d[n];
}

int main() {
    int i,j;
    int a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF) {
        idx=0;
        memset(p,-1,sizeof(p));
        pre[1]=-1;
        memset(used,0,sizeof(used));
        for(i=0; i<m; i++) {
            scanf("%d%d%d",&a,&b,&c);
            used[a][b]=1;
            used[b][a]=1;
            add(a,b,c);
            add(b,a,c);
        }
        int ans=0;
        spfa();
        for(int t=n; pre[t]!=-1; t=pre[t]) {
            used[t][pre[t]]=0;
            used[pre[t]][t]=0;
            int h=work();
            if(h>ans)
                ans=h;
            used[t][pre[t]]=1;
            used[pre[t]][t]=1;
        }
        printf("%d\n",ans);
    }
    return 0;
}




标签:HDU,used,idx,int,路径,mark,1595,cost,find
From: https://blog.51cto.com/u_16192154/6767446

相关文章

  • hdu 1142 A Walk Through the Forest
    WA了好多次了,大概是一直没搞清题意。题意:对边<a,b>,如果a到终点的距离小于b到终点的距离,那么b就可以到a,但是a就不能到b了,所以经过这样的一种筛选的方法之后,我们要在这样的图里寻找能从起点走到终点的路径的总数。思路:先算出每一点到终点的最小距离;然后dfs记忆化搜索路径总数。#incl......
  • hdu 1150 Machine Schedule
    二部图问题:每个任务的两种模式对应一条边,那么最大的匹配数就是最多的任务不用改变模式的任务数。相当于求最小点覆盖,而最小点覆盖=最大匹配数 代码:#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>usingnamespacestd;#defineMAXN110intuN,......
  • hdu Circular Area
    计算两圆相交的面积。参考文章:http://blog.sina.com.cn/s/blog_850498e20100w6fq.html  #include<iostream>#include<cstdio>#include<cstring>#include<cmath>usingnamespacestd;#defineINF0x3fffffff#defineMAXN100001#definepiacos(-1.0)#......
  • hdu 2227 Find the nondecreasing subsequences (树状数组+dp+离散化)
    题意:给定一个长度为n(n<=100000)的整数序列,求其中的递增序列的个数。对于某些序列中的递增序列的个数是可以用dp来求解的,其状态转移方程为:dp[i]=sum(dp[j])+1,j<i&&a[j]<a[i]根据状态转移方程可以得知这样dp的时间复杂度为O(n^2),而对于题目给定的10^6的数量级来说,这样......
  • hdu Polynomial Problem
     有点杂乱无章,考虑各种情况就行了。 #include<iostream>#include<cstdio>#include<cstring>#include<cmath>usingnamespacestd;#defineINF0x3fffffff#defineMAXN100001intmain(){intn,m,x,flag,mul,ans;charstr[MAXN];whil......
  • hdu 1010 Tempter of the Bone (dfs+奇偶剪枝)
    小记:最开始以为是T时间内,用bfsWA了,后来知道是刚好T时间,然后就用dfs,相当于暴力了,然后简单的dfs提交TLE,必须剪枝。首先判最少需要的时间是否有,没有就不用继续了,而如果有,那么因为我们是要花掉T时间刚好到达,那么我们先保证能走到终点的时间,然后在路上花掉多余的时间此时,我们必须保证......
  • 命令_查看占用端口 netstat -ano|findstr "8080"
    查看占用端口 netstat-ano|findstr"8080" tasklist|findstr"12448"netstat-ano|findstr"8080"列说明1:协议 2:本地地址    3:外部地址   4:状态     5:PID查看PID对应的进程名称:tasklist|findstr"12448"......
  • 题解 HDU5726【GCD】/ LGT353762【Soso 的最大公约数】
    Problem给你一个长为\(N(1\leqN\leq1\times10^5)\)的整数序列:\(a_{1},\cdots,a_{n}(0<a_{i}\leq1\times10^9)\)。有\(Q(1\leqQ\leq1\times10^5)\)次提问。每次提问有个范围\(l,r\),你需要计算出\(\gcd(a_{l},,a_{l+1},...,a_{r})\),并且统计数对\((l’,r’......
  • VSCode - go error: gopls was not able to find modules in your workspace
    goplswasnotabletofindmodulesinyourworkspace.WhenoutsideofGOPATH,goplsneedstoknowwhichmodulesyouareworkingon.YoucanfixthisbyopeningyourworkspacetoafolderinsideaGomodule,orbyusingago.workfiletospecifymultiplem......
  • LeetCode 658. Find K Closest Elements 二分+双指针
    Givenasortedintegerarrayarr,twointegerskandx,returnthekclosestintegerstoxinthearray.Theresultshouldalsobesortedinascendingorder.Anintegeraisclosertoxthananintegerbif:|a-x|<|b-x|,or|a-x|==|b-x|an......