首页 » 技术分享 » 小萨的烦恼

小萨的烦恼

　
评论关闭　746次浏览

#题目大意：
Description

圣诞节又要到了！小萨希望和自己心仪的MM一起出去度过一个浪漫的的圣诞节。他进行了详尽的准备，找到了N个很适合他们去约会的好地方，但无奈小萨和他的MM都是初三学校，晚上必须回学校上晚修，没有足够的时间让他们走遍每一个地方。迫于无奈，小萨选择了一个最合适的地方S。小萨打算和他的MM一起步行到那个地方，那样他们就有很多时间来聊天玩乐，但是无奈时间有限，小萨决定坐公共汽车过去。然而，小萨发觉，自己的钱只够买一张公共汽车车票了！小萨该怎么办呢？他找到了你……
【题目描述】
　　小萨将给出一张地图，它可以看做一个有N（N<=100）个结点的图。这张地图有N个公共汽车站，小萨只可以在这N个汽车站上公共汽车。有些车站之间存在一条双向通路，无论是公共汽车还是小萨，都只能走这些通路。若两个车站之间的距离为d，步行所需要的时间为2*d秒，坐公共汽车所需要的时间为d秒。小萨他们只有T秒的时间，他希望你求出他和他的MM出去约会后能否及时赶回来，若不能，则输出“You are day dreaming!”，否则输出他们所需要花费的最少时间。
注意：一张公共汽车车票可以使用两次（只可以搭乘同一辆公共汽车），即可以认为小萨去约会地点的时间和回来的时间相等。

Input

第一行有三个整数N、T、S
接下来是一个N*N的邻接矩阵。两两车站之间的距离不超过10^9。A[I,j]为0表示I和J车站不连通。

Output

若小萨他们不能在限定时间内赶回学校，那么输出“You are day dreaming!”（不包括引号）
否则，输出一个整数，为他们所需要花费的最少时间。

Sample Input

4 5 4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

Sample Output

2

Hint

【数据范围】
20%的数据：N<=10
100%的数据：N<=70 T<=10^9

#解题思路：
我才不会告诉你们他们早恋
好吧，正经点，毕竟都是正经人。
依旧是Floyd算法 O（n^3）

#include <cstdio>
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int f[101][101][3],n,t,s,i,j,k,x;//f[i][j][1]是不坐车，f[i][j][2]是坐车
//其实也没什么好说的了，不懂看看之前的博客（我懒而已）
void read(int &f)  
{  
    f=0;char c;bool d=0;  
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=1;f=f*10+c-48;  
    while (c=getchar(),c>='0'&&c<='9') f=f*10+c-48;  
    if (d) f*=-1;  
}  
void write(int x)  
{  
    if (!x) {putchar(48);return;}  
    if (!(x/10)){putchar(x%10+48);return;}  
    write(x/10);putchar(x%10+48);
}
int min(int x,int y)
{
	return x>y?y:x;
}
int main()
{
	read(n);read(t);read(s);
	r(i,1,n)
	 r(j,1,n)
	  {
	  	read(f[i][j][2]);
	  	if (!f[i][j][2]) f[i][j][2]=9999999;
	  	f[i][j][1]=f[i][j][2]*2;
	  }
	r(k,1,n)
	 r(i,1,n)
	  r(j,1,n)
	   if(i!=j&&i!=k&&j!=k)
	   {
            f[i][j][1]=min(f[i][j][1],f[i][k][1]+f[k][j][1]);
            f[i][j][2]=min(f[i][j][2],f[i][k][2]+f[k][j][1]);
            f[i][j][2]=min(f[i][j][2],f[i][k][1]+f[k][j][2]);
	   }
  x=f[1][s][2]*2;
  if (x<=t)
   write(x);
  else printf("You are day dreaming!");
  return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：小萨的烦恼，转载请注明来源！

赞 0