hdu 2680 Dijstra
2024-09-01 15:44:15
Choose the best route
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13229 Accepted Submission(s): 4280
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.
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
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
-1
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 0x3f3f3f3f
using namespace std;
int map[][],d[],n,m,s,t;
void dijkstra(int x)
{
int i,j,min,mark,used[];
for(i=;i<=n;i++)
{
used[i]=;
d[i]=map[x][i];
}
d[x]=;
used[x]=;
for(i=;i<=n;i++)
{
min=MAX;
mark=-;
for(j=;j<=n;j++)
{
if(!used[j]&&d[j]<min)
{
min=d[j];
mark=j;
}
}
if(mark==-)
break;
used[mark]=;
for(j=;j<=n;j++)
{
if(!used[j]&&d[j]>d[mark]+map[mark][j])
d[j]=d[mark]+map[mark][j];
}
} }
int main()
{
int a,b,c,i,j;
while(scanf("%d%d%d",&n,&m,&s)!=EOF)
{
memset(map,MAX,sizeof(map));
for(i=;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[b][a]>c)
map[b][a]=c;
}
dijkstra(s);
int start;
int mi=MAX;
scanf("%d",&t);
for(i=;i<t;i++)
{
scanf("%d",&start);
mi=mi<d[start]?mi:d[start];
}
if(mi==MAX)
printf("-1\n");
else
printf("%d\n",mi);
}
return;
}
最新文章
- JavaScript 函数声明,函数表达式,匿名函数,立即执行函数之区别
- mysql中DATETIME,DATE和TIMESTAMP的区别整理
- org.apache.http.conn.HttpHostConnectException: Connection to http://localhost refused in android
- hdu 1028 Ignatius and the Princess III(DP)
- Cocos2d-x 3.0修改Android平台帧率fps - 解决游戏运行手机发热发烫问题
- Python数据类型之列表
- 使用GDI+轻松创建缩略图
- Java——(五)Collection之List集合、ArrayList和Vector实现类
- Struts2返回Json数据(使用Struts2插件)
- Java设计模式之包装模式
- 优化设计提高sql类数据库的性能
- Exception in thread ";main"; org.I0Itec.zkclient.exception.ZkAuthFailedException: Authentication failure is thrown while creating kafka topic
- 获取安卓应用APK包名的方法
- [Swift]LeetCode463. 岛屿的周长 | Island Perimeter
- 快递单号自动识别接口API-trackingmore
- 【摘】Oracle执行计划不走索引的原因总结
- HDU3032 Nim or not Nim?
- Qt自定义阴影效果和QOpenGLWidget冲突导致控件不刷新
- django-celery使用
- ob