hdu-2680-Choose the best route(dijkstra)

简介: hdu-2680-Choose the best route(dijkstra)


Choose the best route

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10470    Accepted Submission(s): 3367


Problem Description

One day , Kiki wants to visit one of her friends. As she is liable to carsickness , she wants to arrive at her friend’s home as soon as possible . Now give you a map of the city’s traffic route, and the stations which are near Kiki’s home so that she can take. You may suppose Kiki can change the bus at any station. Please find out the least time Kiki needs to spend. To make it easy, if the city have n bus stations ,the stations will been expressed as an integer 1,2,3…n.

 


Input

There are several test cases.

Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.

Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .

Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.

 


Output

The output contains one line for each data set : the least time Kiki needs to spend ,if it’s impossible to find such a route ,just output “-1”.

 


Sample Input

      5 8 5 1 2 2 1 5 3 1 3 4 2 4 7 2 5 6 2 3 5 3 5 1 4 5 1 2 2 3 4 3 4 1 2 3 1 3 4 2 3 2 1 1      

 


Sample Output

      1 -1      

 


Author

dandelion

 


Source

2009浙江大学计算机研考复试(机试部分)——全真模拟

 


Recommend

lcy   |   We have carefully selected several similar problems for you:   2112  2544  1217  1142  1385

 


题目分析:

也是走模板但是要注意了,这个是单向图,好好看看单向图是怎么建表的


#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
#define M 1010
using namespace std;
int mark[M],dis[M],time[M][M];
int n,m,s;
void dijkstra(int s)
{
  memset(mark,0,sizeof(mark));
  memset(dis,INF,sizeof(dis));
  dis[s]=0;
  while(1)
  {
    int v=-1;
    for(int i=1;i<=n;i++)
        if(!mark[i]&&(v==-1||dis[i]<dis[v]))
           v=i;
    if(v==-1)  break;
    mark[v]=1;
    for(int i=1;i<=n;i++)
         dis[i]=min(dis[i],dis[v]+time[v][i]);
  }
}
int main()
{
  while(~scanf("%d%d%d",&n,&m,&s))
  {
    memset(time,INF,sizeof(time));
    while(m--)
    {
      int a,b,c;
      scanf("%d%d%d",&a,&b,&c);
      if(time[b][a]>c&&a!=b)
        time[b][a]=c;// 对就这里  单向建就行了,我这里是从终点查起点了所以反向建了
    }
    int w,st[M];
    scanf("%d",&w);
    for(int i=1;i<=w;i++)
      scanf("%d",&st[i]);
    int minn=INF;
    dijkstra(s);//  因为就一个终点但是起点不是一个,所以反向查比较省时间
    for(int i=1;i<=w;i++)
        minn=min(minn,dis[st[i]]);
      if(minn==INF)  printf("-1\n");
      else 
    printf("%d\n",minn);
  }
  return 0;
}


目录
相关文章
|
11月前
|
NoSQL 编译器 C语言
C语言调试是开发中的重要技能,涵盖基本技巧如打印输出、断点调试和单步执行,以及使用GCC、GDB、Visual Studio和Eclipse CDT等工具。
C语言调试是开发中的重要技能,涵盖基本技巧如打印输出、断点调试和单步执行,以及使用GCC、GDB、Visual Studio和Eclipse CDT等工具。高级技巧包括内存检查、性能分析和符号调试。通过实践案例学习如何有效定位和解决问题,同时注意保持耐心、合理利用工具、记录过程并避免过度调试,以提高编程能力和开发效率。
274 1
|
前端开发 JavaScript PHP
在多文件上传中,处理文件大小限制
【5月更文挑战第3天】在多文件上传时,为限制文件大小,通常会在前端(JavaScript,如jQuery示例)和后端(如PHP)实施检查。前端检查防止超大文件上传,后端验证确保接收文件符合大小限制,两者结合以增强安全性。
291 1
|
监控 Java 开发者
JDK 9新特性深度解析:垃圾回收器的改进与优化
本文将深入探讨JDK 9中垃圾回收器的改进与优化。随着Java语言的不断发展,垃圾回收器作为内存管理的核心组件也经历了多次迭代和改进。JDK 9引入了新的垃圾回收器,旨在提高内存回收的效率和性能,降低垃圾回收的停顿时间。本文将详细介绍这些改进,以及如何在实际应用中利用这些改进来提高应用程序的性能和稳定性。
|
Kubernetes Java Docker
使用Kubernetes部署Spring Boot应用的实践
使用Kubernetes部署Spring Boot应用的实践
|
Web App开发 算法 PyTorch
vLLM部署Yuan2.0:高吞吐、更便捷
vLLM是UC Berkeley开源的大语言模型高速推理框架,其内存管理核心——PagedAttention、内置的加速算法如Continues Batching等,一方面可以提升Yuan2.0模型推理部署时的内存使用效率,另一方面可以大幅提升在实时应用场景下Yuan2.0的吞吐量。
|
SQL 分布式计算 Apache
Apache Superset
Apache Superset
|
前端开发 JavaScript Java
JavaFX学习笔记(二) 关键特性与基本概念
JavaFX学习笔记(二) 关键特性与基本概念
|
安全 数据可视化 数据安全/隐私保护
猿创征文|docker本地私人仓库快速搭建后的安全优化(用户鉴权和简易的web界面开启)
猿创征文|docker本地私人仓库快速搭建后的安全优化(用户鉴权和简易的web界面开启)
242 0
|
存储 运维 小程序
微信小程序云开发 初学者入门教程一
微信小程序云开发 初学者入门教程一
357 0
|
存储 缓存 Java
(七)Spring源码解析:Spring事务
(七)Spring源码解析:Spring事务
256 1