题目描述:
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 828题目链接:http://acm.hdu.edu.cn/show ... -
杭电1596 迪杰特斯拉算法的应用
2012-07-25 20:47 1038题目 Problem Description XX星球有很多 ... -
杭电1272
2012-07-18 15:13 797这道题主要就是判断一下有没有环,还有就是节点数减去边数等于1, ... -
杭电2544 最短路径
2012-07-17 17:31 835Problem Description 在每年的校赛里,所有进 ... -
迪杰斯特拉(Dijkstra)算法
2012-07-17 16:07 1435迪杰斯特拉算法 迪杰斯特拉(Dijkstra)算法思想 ... -
杭电acm部分题目分类
2012-07-07 16:38 3394注:DP代表动态规划 1001 这个就不用说了吧 ... -
动态规划之背包问题
2012-07-07 16:22 816/*在一固定容积为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 905#include<stdio.h> int mai ... -
动态规划
2012-07-07 10:21 713动态规划算法 一、基本 ...
相关推荐
图-6-迪杰特斯拉算法.cpp
迪杰斯特拉算法可以基于某一载体进行优化,本文主要是基于城市道路载体,希望对大家能有帮助。
迪杰斯特拉算法求i额最短路问题,经典算法。
利用matlab软件实现迪杰斯特拉算法求最短路径
实现迪杰斯特拉算法 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; //源点已...
数据结构中的关键路径实现,可视化界面,迪杰斯特拉算法,和弗洛伊德算法
迪杰斯特拉算法的Java实现
实现最小生成树 最短路径 floyd 广搜 深搜 迪杰斯特拉算法
期末数据库课程设计 《火车出行路线规划及售票系统》 利用迪杰斯特拉算法找到最省钱的城市路线(只是城市路线) 采用简单工厂模式进行设计用户操作
最短路问题迪杰斯特拉算法PPT课件.pptx
迪杰斯特拉算法算法步骤: (1)初始时,S只包含源点。 (2)从U中选取一个距离v最小的顶点k加入S中(该选定的距离就是v到k的最短路径长度)。 (3)以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到...
单源最短路径 贝尔曼福特 和 迪杰斯特拉 算法的实现
最短路课设,实现最短路算法,用迪杰斯特拉算法实现
迪杰斯特拉算法或者floyd算法,我不记得具体是哪个了,但肯定是生成最短路径矩阵的函数
用MATLAB实现迪杰斯特拉算法来寻找最短路径,压缩包中DIJ为算法的执行程序,SymMatrix为将邻接矩阵补齐为对称矩阵的程序,两个graph文件存储的两个邻接矩阵,DIJ加载了其中一个进行计算。也可以自己重新编辑邻接矩阵...
迪杰斯特拉算法计算城市与城市间时间最短,距离最短的路线,并用百度地图进行可视化
C语言实现迪杰斯特拉算法,亲测好用,放在正确的环境下就可运行
迪杰斯特拉算法,matlab可跑,供参考使用学习
数据结构与算法中图求最短路径,迪杰斯特拉算法的实现,带详细注释,可完整实现。
通过邻接矩阵的数据结构存储一副图结构。利用迪杰斯特拉算法(C++实现)求其最短路径。