题目描述:
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
注意细节(红色字体)···
AC代码·····
*********************************************
#include"stdio.h"
#include"string.h"
#define MAX 10000000
int time[1001],map[1001][1001],mark[1001];
int main()
{
int n,m,p,q,s,t,i,j,k,W,w,sum,min;
while(scanf("%d%d%d",&n,&m,&s)!=EOF)
{
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
map[i][j]=MAX;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&p,&q,&t);
if(map[p][q]>t)
map[p][q]=t;
}
scanf("%d",&W);
sum=MAX;
for(i=0;i<W;i++)
{
scanf("%d",&w);
map[0][w]=0;
}
memset(mark,0,sizeof(mark));
for(j=0;j<=n;j++)
time[j]=map[0][j];
time[0]=0;
mark[0]=1;
for(j=0;j<=n;j++)
{
min=MAX;
for(k=0;k<=n;k++)
{
if(mark[k]==0&&time[k]<min)
{
min=time[k];
t=k;
}
}
if(min==MAX)
break;
mark[t]=1;
for(k=0;k<=n;k++)
{
if(!mark[k]&&time[k]>(time[t]+map[t][k]))
time[k]=time[t]+map[t][k];
}
}
if(sum>time[s])
sum=time[s];
if(sum==MAX)
printf("-1\n");
else
printf("%d\n",sum);
}
return 0;
}
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
注意细节(红色字体)···
AC代码·····
*********************************************
#include"stdio.h"
#include"string.h"
#define MAX 10000000
int time[1001],map[1001][1001],mark[1001];
int main()
{
int n,m,p,q,s,t,i,j,k,W,w,sum,min;
while(scanf("%d%d%d",&n,&m,&s)!=EOF)
{
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
map[i][j]=MAX;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&p,&q,&t);
if(map[p][q]>t)
map[p][q]=t;
}
scanf("%d",&W);
sum=MAX;
for(i=0;i<W;i++)
{
scanf("%d",&w);
map[0][w]=0;
}
memset(mark,0,sizeof(mark));
for(j=0;j<=n;j++)
time[j]=map[0][j];
time[0]=0;
mark[0]=1;
for(j=0;j<=n;j++)
{
min=MAX;
for(k=0;k<=n;k++)
{
if(mark[k]==0&&time[k]<min)
{
min=time[k];
t=k;
}
}
if(min==MAX)
break;
mark[t]=1;
for(k=0;k<=n;k++)
{
if(!mark[k]&&time[k]>(time[t]+map[t][k]))
time[k]=time[t]+map[t][k];
}
}
if(sum>time[s])
sum=time[s];
if(sum==MAX)
printf("-1\n");
else
printf("%d\n",sum);
}
return 0;
}
发表评论
-
杭电1162 最小生成树问题
2012-07-27 15:15 859题目链接:http://acm.hdu.edu.cn/show ... -
杭电1596 迪杰特斯拉算法的应用
2012-07-25 20:47 1068题目 Problem Description XX星球有很多 ... -
杭电1272
2012-07-18 15:13 832这道题主要就是判断一下有没有环,还有就是节点数减去边数等于1, ... -
杭电2544 最短路径
2012-07-17 17:31 861Problem Description 在每年的校赛里,所有进 ... -
迪杰斯特拉(Dijkstra)算法
2012-07-17 16:07 1466迪杰斯特拉算法 迪杰斯特拉(Dijkstra)算法思想 ... -
杭电acm部分题目分类
2012-07-07 16:38 3433注:DP代表动态规划 1001 这个就不用说了吧 ... -
动态规划之背包问题
2012-07-07 16:22 843/*在一固定容积为C的背包内装入N件物品, 物品的体积为:w ... -
动态规划之背包问题
2012-07-07 16:12 0/*在一固定容积为C的背包内装入N件物品, 物品的体积为:w1 ... -
背包问题
2012-07-07 10:44 0决策是:第N件物品放或者不放; 由此可以写出动态转移方 ... -
杭电1003代码
2012-07-07 10:24 942#include<stdio.h> int mai ... -
动态规划
2012-07-07 10:21 750动态规划算法 一、基本 ...
相关推荐
图-6-迪杰特斯拉算法.cpp
Python2.7,迪杰特斯拉算法_Python_Dijkstra
迪杰斯特拉(Dijkstra)算法是图论中的一个著名算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。这个算法主要用于解决单源最短路径问题,即从图中的一点(源点)出发,找到到达其他所有点的最短路径。在...
迪杰斯特拉算法的应用背景包括管道铺设、线路安排、厂区布局、设备更新等领域。 迪杰斯特拉算法的思路: 迪杰斯特拉算法的思路是从始点出发,逐步顺序地向外探寻,每向外延伸一步都要求是最短的。这意味着,算法会...
迪杰斯特拉算法可以基于某一载体进行优化,本文主要是基于城市道路载体,希望对大家能有帮助。
迪杰斯特拉(Dijkstra)算法是图论中一个经典的单源最短路径算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。这个算法主要用于解决带权重的有向图中从某一点到其余所有点的最短路径问题。在本案例中,我们...
总的来说,关键路径、迪杰斯特拉算法和弗洛伊德算法是解决路径优化问题的关键工具,广泛应用于项目管理、网络路由、地图导航等领域。结合MFC进行可视化开发,不仅可以提升学习的趣味性,也有助于提升编程和问题解决...
在实际应用中,迪杰斯特拉算法可能会遇到一些优化问题,例如负权边的存在会导致算法失效,这时需要采用其他算法如Bellman-Ford。此外,对于稀疏图(边的数量远小于节点数量的平方),使用邻接表可以节省空间。 总之...
以下是关于迪杰斯特拉算法的详细介绍以及如何应用于这个课设。 **迪杰斯特拉算法**: 迪杰斯特拉算法由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。它是一种贪心算法,每次选择当前未访问节点中距离源节点...
迪杰斯特拉(Dijkstra)算法则是图论中的一种著名算法,用于寻找带权有向图中从一个源节点到其他所有节点的最短路径。在本项目中,我们将深入探讨这个算法及其在数据结构中的应用。 迪杰斯特拉算法的基本思想是使用...
在本数据库课程设计中,我们关注的是《火车出行路线规划及售票系统》,这是一个结合了算法与数据库技术的实际应用项目。核心算法是迪杰斯特拉(Dijkstra)算法,它用于解决最短路径问题,帮助用户找到从一个城市到另...
7S迪杰斯特拉算法可能是对原算法的一种特定实现或者是在解决特定问题时的应用。 在迪杰斯特拉算法中,主要步骤如下: 1. 初始化:选择一个起始节点(通常称为源节点),将该节点的距离设为0,其他所有节点的距离设...
实现迪杰斯特拉算法 Dijkstra void main() { //设置初值 int u=1; //设源点的序号为1 for(int i=0; i; i++) { Visited[i]=0; path[i]=u-1; Distance[i]=Graph[u-1][i]; } Visited[u-1]=1; //源点已...
在实际应用中,迪杰斯特拉算法常用于解决网络路由、交通导航、社交网络分析等多种问题,例如计算互联网中两台计算机之间的最短路由,或者找出城市之间驾车的最短路线。其效率在优化后的实现下可以达到线性时间复杂度...
10. **实际应用**:迪杰斯特拉算法广泛应用于网络路由、GPS导航、社会网络分析等领域,寻找两点间最短的通信路径或最少的费用路径。 通过理解和实现迪杰斯特拉算法,我们可以学习到图的表示方法、优先队列的使用...
用MATLAB实现迪杰斯特拉算法来寻找最短路径,压缩包中DIJ为算法的执行程序,SymMatrix为将邻接矩阵补齐为对称矩阵的程序,两个graph文件存储的两个邻接矩阵,DIJ加载了其中一个进行计算。也可以自己重新编辑邻接矩阵...
在实际应用中,它广泛用于路由、网络优化以及图形算法等领域。这个算法的核心思想是通过不断更新节点的最短路径来逐步构建全局的最短路径树。 在给定的“使用标准模板库写迪杰斯特拉算法”中,我们重点关注两个关键...
迪杰斯特拉算法是由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出的,它是一种解决单源最短路径问题的算法,特别适用于加权有向图或无向图。该算法的基本思想是从起始节点开始,逐步扩展到相邻节点,每次选取当前...
迪杰斯科拉(Dijkstra)算法是一种在加权图中寻找最短路径的经典算法,由荷兰计算机科学家艾兹格·迪杰斯科拉在1956年提出。这个算法主要用于解决单源最短路径问题,即从图中的一个特定顶点(源点)出发,找到到达...
迪杰斯特拉(Dijkstra)算法是解决单源最短路径问题的一种经典算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。它主要用于寻找图中一个起点到其他所有点的最短路径。在这个例子中,问题是要帮助Kiki找到从...