专栏首页Zaqdt_ACMHDU3790 最短路径问题(dijkstra+思维)

HDU3790 最短路径问题(dijkstra+思维)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3790

       其实就是裸的dij,只不过加了一个数组用来存花费,而且需要注意的是因为要求最短路程的最少花费,所以需要在松弛的时候对花费进行更新操作,当时没有加这个wa了n发...


AC代码:

#include <bits/stdc++.h>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,num,s,t;
struct Node{
  int to,w,next,l;
  bool operator < (const Node &a) const{
    return a.l < l;
  }
}Edge[maxn],Now,Next;
int head[maxn];

void init(){
  memset(head,-1,sizeof(head));
  num = 0;
}

void add(int u,int v,int l,int w){
  Edge[num].to = v;
  Edge[num].w = w;
  Edge[num].l = l;
  Edge[num].next = head[u];
  head[u] = num++;
}

void dijkstra(int x){
  bool vis[maxn];
  int dist[maxn];
  int cost[maxn];
  memset(cost,0,sizeof(cost));
  memset(dist,inf,sizeof(dist));
  memset(vis,false,sizeof(vis));
  priority_queue<Node> q;
  Now.to = x;
  Now.w = 0;
  Now.next = 0;
  dist[x] = 0;
  q.push(Now);
  while(!q.empty()){
    Now = q.top();
    q.pop();
    int ans = Now.to;
    if(vis[ans])
      continue;
    vis[ans] = true;
    for(int i=head[ans];i!=-1;i=Edge[i].next){
      int u = Edge[i].to;
      if(!vis[u] && dist[u] > dist[ans] + Edge[i].l){
        dist[u] = dist[ans] + Edge[i].l;
        cost[u] = cost[ans] + Edge[i].w;
      }
      else if(!vis[u] && dist[u] == dist[ans] + Edge[i].l && cost[u] > cost[ans] + Edge[i].w){
        cost[u] = cost[ans] + Edge[i].w;
      }
      Next.to = u;
      Next.w = cost[u];
      Next.l = dist[u];
      q.push(Next);
    }
  }
  printf("%d %d\n",dist[t], cost[t]);
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    if(n == 0 && m == 0)break;
    init();
    for(int i=0;i<m;i++){
      int u,v,w,l;
      scanf("%d%d%d%d",&u,&v,&l,&w);
      add(u, v, l, w);
      add(v, u, l, w);
    }
    scanf("%d%d",&s,&t);
    dijkstra(s);
  }
  return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 3339 In Action(dijkstra+01背包)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3339

    Ch_Zaqdt
  • HDU 1839 Delay Constrained Maximum Capacity Path(dijkstra+二分)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1839

    Ch_Zaqdt
  • Codeforces Round #541 (Div. 2) B. Draw!(思维)

    题目链接:https://codeforces.com/contest/1131/problem/B

    Ch_Zaqdt
  • 分布式入门,怎样用PyTorch实现多GPU分布式训练

    具体来讲,本文首先介绍了分布式计算的基本概念,以及分布式计算如何用于深度学习。然后,列举了配置处理分布式应用的环境的标准需求(硬件和软件)。最后,为了提供亲身实...

    机器之心
  • 开源TBase编译部署详细步骤

    很多学员想学习TBase数据库,但是苦于没有企业版的授权文件,在编译部署开源版本的时候又遇到诸多问题,因此我写下这篇文章供大家参考。

    腾讯云数据库 TencentDB
  • MyEclipse开发第一个java程序HelloWorld

    图2_...

    马克java社区
  • 一分钟了解负载均衡的一切

    什么是负载均衡 负载均衡(Load Balance)是分布式系统架构设计中必须考虑的因素之一,它通常是指,将请求/数据【均匀】分摊到多个操作单元上执行,负载均...

    架构师之路
  • for循环输出杨辉三角

    葆宁
  • excel中的超链接函数

    今天跟大家分享在excel中超链接函数的用法! ▼ 其实excel中想要达到超链接效果有很多种方法:直接手工设置、超链接函数、开发工具、VBA等都可以实现。但是...

    数据小磨坊
  • Webshell免杀套路

    字符串变形多数用于BYPASS安全狗,相当对于D盾,安全狗更加重视"形" 一个特殊的变形就能绕过安全狗,看看PHP手册,有着很多关于操作字符串的函数

    HACK学习

扫码关注云+社区

领取腾讯云代金券