博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Fzu月赛11 老S的旅行计划 dij
阅读量:5874 次
发布时间:2019-06-19

本文共 2615 字,大约阅读时间需要 8 分钟。

Description

老S在某城市生活的非常不自在,想趁着ICPC举办期间在省内转转。已知老S所在的省有N个城市,M条无向边(对于某一对结点可能出现重边)。由于省内的交通相当糟糕,通过某条边所需要花费的时间受到一天中不同时刻的影响。此外对于某一时刻(一天24小时的任意一个整点算一个时刻),从任何方向通过无向边所需要的时间相同。现在老S想请你帮他规划一下旅行路线。

Input

 

第一行输入为一个整数T表示测试个数T

对于每一个测试的第一行为3个整数N,M,K,其中K表示老S的询问数

之后有2M行,一组2行共M组。每组第一行是两个整数x,y表示第x个城市与第y个城市之间有一条无向边。

每组第二行有24个整数cost[i](0<=i<=23)表示在第i个时刻通过这条无向边需要消耗的时间(单位为小时)。并且保证cost[i]<=coust[i+1]+1(0<=i<=22)且cost[23]<=cost[0]+1。

之后有K每行有两个整数D和S表示询问,从1号城市的第S个时刻出发,最终目的地为城市D所需要最少几个小时,此外如果老S不能到达目标城市则输出-1。

Limit:

1 <=x, y<=N.

1 <=all Cost values<=50.

1 <=D<=N.

0 <=S<=23.

1 <=T<=100.

2 <=N<= 20.

1 <=M<=100.

1 <=K<= 100.

Output

对于任意一个样例输出仅有一行包括"Case #x: "其中x表示第x个样例,之后有K个整数用空格分隔开,分别表示老S的K个询问的答案。

Sample Input

3 3 3 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 3 3 3 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 3 4 3 3 3 1 2 7 23 23 25 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 1 3 10 11 15 26 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 2 3 7 29 28 27 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 2 14 3 3 3 21

Sample Output

Case #1: 1 2
Case #2: 1 -1
Case #3: 17 26 13
 
G[k][u][v]表示在第k个时刻边u-v的权值,对于每个询问,设now表示到达当前节点的最小时间,然后每次dij取到最小时间d[x]时,用(S + d[x]) % 24作为当前边权值来更新即可
#include 
#include
#include
#include
#include
#include
using namespace std;const int INF = 0x3f3f3f3f;const int N = 50;int d[N], v[N], G[30][N][N];int n, m, k;void init() { for(int t = 0; t <= 25; ++t) for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) G[t][i][j] = INF;}void dij(int S){ memset(v, 0, sizeof v); for(int i = 0; i < n; ++i) d[i] = INF; d[0] = 0; int now; for(int i = 0; i < n; ++i) { int x, m = INF; for(int y = 0; y < n; ++y) if(!v[y] && d[y] <= m) m = d[x = y]; v[x] = 1; now = (S + d[x]) % 24; for(int y = 0; y < n; ++y) if(G[now][x][y] != INF) { d[y] = min(d[y], d[x] + G[now][x][y]); } } // for(int i = 0; i < n; ++i) printf("%d ", d[i]); puts("");}int main(){ int _, cas = 1; scanf("%d", &_); while(_ --) { scanf("%d%d%d", &n, &m, &k); int u, v, c; init(); while(m --) { scanf("%d%d", &u, &v); --u; --v; for(int i = 0; i <= 23; ++i) { scanf("%d", &c); G[i][v][u] = G[i][u][v] = min(c, G[i][u][v]); } } printf("Case #%d:", cas++); int D, S; while(k --) { scanf("%d%d", &D, &S); --D; dij(S); if(d[D] == INF) printf(" -1"); else printf(" %d", d[D]); } puts(""); } return 0;}

 

转载于:https://www.cnblogs.com/orchidzjl/p/4978803.html

你可能感兴趣的文章
PHP-mysqllib和mysqlnd
查看>>
Redis常用命令
查看>>
NeHe OpenGL教程 第三十五课:播放AVI
查看>>
Linux下ping命令、traceroute命令、tracert命令的使用
查看>>
js replace,正则截取字符串内容
查看>>
socket
查看>>
Highcharts使用表格数据绘制图表
查看>>
Thinkphp5笔记三:创建基类
查看>>
LNMP之编译安装PHP出现的问题
查看>>
hdu5373
查看>>
4.单链表的创建和建立
查看>>
testng生成报告 testng-xslt 美化测试报告
查看>>
Android 好看的搜索界面,大赞Animation
查看>>
查询反模式 - GroupBy、HAVING的理解
查看>>
[转]动态加载javascript
查看>>
【协议】5、gossip 协议
查看>>
基于配置文件的redis的主从复制
查看>>
hasura graphql 角色访问控制
查看>>
springmvc中controller内方法跳转forward?redirect?
查看>>
C#委托,事件理解入门 (译稿)转载
查看>>