|
Memory Limit: 32768 KB Special Judge Scandinavians often make vacation during the Easter holidays in the largest ski resort Are. Are provides fantastic ski conditions, many ski lifts and slopes of various difficulty profiles. However, some lifts go faster than others, and some are so popular Per is a beginner skier and he is afraid of lifts, even though he wants to ski as much as possible. Now he sees that he can take several different lifts and then many different slopes or some other lifts, and this freedom of choice is starting to be too
Can you help Per find the least scary ski journey? A ski resort contains n places, m slopes, and k lifts (2 <= n <= 1000, 1 <= m <= 1000, 1 <= k <= 1000). The slopes and lifts always lead from some place to another place: the slopes lead from places with Input The first line of the input contains the number of cases - the number of ski resorts to process. Each ski resort is described as follows: the first line contains three integers n, m, and k. The following m lines describe the slopes: each line contains three Output For each input case, the program should print two lines. The first line should contain a space-separated list of places in the order they will be visited - the first place should be the same as the last place. The second line should contain the ratio of Sample Input 1 5 4 3 1 3 12 2 3 6 3 4 9 5 4 9 4 5 12 5 1 12 4 2 18 Sample Output 4 5 1 3 4 0.875 Source: Norgesmesterskapet i Programmering,2004 |
题意：
给你一个滑雪场，有两种边（用雪橇上升可看做一种边，从雪坡滑下来可看做一种边），让你找到两点A、B，A->B为经过第一种边上去，所需时间t1，B->A为经过第二种边下来，所需时间t2，使得t2/t1最大。
思路：
用两种边分别建两个图，用n次SPFA找到一个图中的任意一点到任意一点的最短路，再用n次SPFA找到另一个图中的任意一点到任意一点的最长路，然后枚举取得t2/t1的最大值就够了。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 1005
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,cnt,sx,cxx;
double ans;
bool vis[maxn];
int p[maxn];
int dist1[maxn][maxn],dist2[maxn][maxn];
int path1[maxn][maxn],path2[maxn][maxn];
struct Node
{
int r,cost;
int next;
}edge1[maxn],edge2[maxn];
queue<int>q;
void init()
{
memset(p,0,sizeof(p));
memset(path1,0,sizeof(path1));
memset(path2,0,sizeof(path2));
memset(dist1,0,sizeof(dist1));
memset(dist2,0x3f,sizeof(dist2));
}
void addedge1(int u,int v,int w) // 建第一个图
{
cnt++;
edge1[cnt].r=v;
edge1[cnt].cost=w;
edge1[cnt].next=p[u];
p[u]=cnt;
}
void addedge2(int u,int v,int w) // 建第二个图
{
cnt++;
edge2[cnt].r=v;
edge2[cnt].cost=w;
edge2[cnt].next=p[u];
p[u]=cnt;
}
void SPFA1(int k) // 找最长路 初始化最小 遇见大的更新
{
int i,j,nx;
memset(vis,0,sizeof(vis));
sx=k;
while(!q.empty()) q.pop();
path1[sx][sx]=sx;
dist1[sx][sx]=0;
vis[sx]=1;
q.push(sx);
while(!q.empty())
{
nx=q.front();
vis[nx]=0;
q.pop();
for(i=p[nx];i;i=edge1[i].next)
{
if(dist1[sx][edge1[i].r]<dist1[sx][nx]+edge1[i].cost)
{
dist1[sx][edge1[i].r]=dist1[sx][nx]+edge1[i].cost;
path1[sx][edge1[i].r]=nx;
if(!vis[edge1[i].r])
{
vis[edge1[i].r]=1;
q.push(edge1[i].r);
}
}
}
}
}
void SPFA2(int k) // 找最短路 初始化最大 遇见小的更新
{
int i,j,nx;
memset(vis,0,sizeof(vis));
sx=k;
while(!q.empty()) q.pop();
path2[sx][sx]=sx;
dist2[sx][sx]=0;
vis[sx]=1;
q.push(sx);
while(!q.empty())
{
nx=q.front();
vis[nx]=0;
q.pop();
for(i=p[nx];i;i=edge2[i].next)
{
if(dist2[sx][edge2[i].r]>dist2[sx][nx]+edge2[i].cost)
{
dist2[sx][edge2[i].r]=dist2[sx][nx]+edge2[i].cost;
path2[sx][edge2[i].r]=nx;
if(!vis[edge2[i].r])
{
vis[edge2[i].r]=1;
q.push(edge2[i].r);
}
}
}
}
}
void output1(int e,int s) // 打印路径1
{
if(e==s) return ;
else
{
output1(path1[s][e],s);
printf(" %d",e);
}
}
void output2(int e,int s) // 打印路径2
{
if(e==s) printf("%d",e);
else
{
output2(path2[s][e],s);
printf(" %d",e);
}
}
int main()
{
int i,j,t,u,v,w,s,e;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&cxx);
init();
cnt=0;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge1(u,v,w);
}
for(i=1;i<=n;i++)
{
SPFA1(i);
}
cnt=0;
memset(p,0,sizeof(p));
for(i=1;i<=cxx;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge2(u,v,w);
}
for(i=1;i<=n;i++)
{
SPFA2(i);
}
ans=0;
for(i=1;i<=n;i++) // 更新ans
{
for(j=1;j<=n;j++)
{
if(i==j||dist2[i][j]==INF) continue ;
if(dist1[j][i]*1.0/dist2[i][j]>ans)
{
s=i,e=j;
ans=dist1[j][i]*1.0/dist2[i][j];
}
}
}
output2(e,s);
output1(s,e);
printf("\n%.3f\n",ans);
}
return 0;
}