「TJOJ1110」菜哭武读论文

April 22, 2018

题目描述

新格尔公司的天才程序员刚刚接了一个特别厉害的项目，所以他最近正在阅读论文找灵感。菜哭武有一个习惯就是每天给自己定一个小目标，不完成这个小目标不睡觉。

读论文期间，他把自己找到的相关的论文都编了号从1 号到1,000号，每天读一部分。

比如说今天的任务就是从编号a读到b的论文。但是今天菜哭武的心情不大好，所以他不想每一篇都读，所以他准备准备阅读编号为 a和 b的以及其中的一部分论文，并且阅读顺序有些要求，如果他读完了编号为 i的论文，那么他下一篇可以选择阅读编号为 i-2,，i+2，或者 i*2三者中的任意一篇（当然了,编号不在[1，1,000] 范围内的论文他是不会看的，但是他有可能会去看编号在[a, b]之外的论文），菜哭武读论文的速度非常快，可以忽略，但是读两篇论文之间他需要休息，休息的时间取决于他下一篇选取了哪篇论文，如果选择编号为 i*2的，那么需要休息 x分钟；如果选择编号为 i+2的需要休息 y分钟；如果选择了 i-2的需要休息 z分钟。那么他想知道今天按照他的方式从 a编号的论文开始读，直到读完 b编号的论文，最少需要多少分钟。

天才程序员菜哭武自然是会算的，但是他最近心情不好呀，不想算，所以需要你帮帮忙。

输入

题目包含多组数据。

输入的第一行有一个整数 T (1≤T≤10) 代表有 T组数据。

对于每组数据分为两行：

第一行有两个整数 a,b (1≤a,b≤1,000)。

第二行有三个整数 x,y,z (1≤x,y,z≤1,000)。

输出

对于每组数据，输出的第一行为 Case #x: ,其中 x是数据编号（从1开始），

第二行，有一个整数，最少花的时间，如果永远不可能达到小目标，输出-1。

样例输入

样例输出

Case #1:
9
Case #2:
-1
Case #3:
2
Case #4:
10

题解

把1-1000当成点，休息时间当成边权，跑最短路就行了。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <cstdio> 
#include <cmath> 
#include <cstring> 
using namespace std;

int s, t, u, x, y, z;
int w[1001][1001], dis[1001];
bool pd[1001][1001], used[1001];
int main()
{
	freopen("a.txt", "r", stdin);
	cin >> u;
	for (int pp = 1; pp <= u; pp++)
	{
		memset(w, 0, sizeof(w));
		memset(used, 0, sizeof(used));
		memset(pd, 0, sizeof(pd));
		memset(dis, 127, sizeof(dis));

		scanf("%d %d", &s, &t);
		cin >> x >> y >> z;

		for (int i = 1; i <= 998; i++)
		{
			w[i][i + 2] = y;
			pd[i][i + 2] = 1;
		}
		for (int i = 3; i <= 1000; i++)
		{
			w[i][i - 2] = z;
			pd[i][i - 2] = 1;
		}
		for (int i = 1; i <= 500; i++)
		{
			w[i][i * 2] = x;
			pd[i][i * 2] = 1;
		}

		dis[s] = 0;
		for (int i = 1; i <= 1000; i++)
		{
			int mini = 0;
			for (int j = 1; j <= 1000; j++)
				if (!used[j] && dis[j] < dis[mini])
					mini = j;
			if (mini == 0)
				break;
			used[mini] = 1;
			for (int j = 1; j <= 1000; j++)
				if (pd[mini][j] && dis[mini] + w[mini][j] < dis[j])
					dis[j] = dis[mini] + w[mini][j];
		}
		cout << "Case #" << pp << ":" << endl;

		if (dis[t] <= (1 << 30))
			printf("%d", dis[t]);
		else
			printf("-1");

		if (pp != u)
			printf("\n");
	}
	return 0;
}