NC24161. [USACO 2015 Jan S]Cow Routing
描述
输入描述
The first line of input contains A, B, and N, separated by spaces.
The next 2N lines describe the available routes, in two lines per
route. The first line contains the cost of using the route (an integer
in the range 1..1,000,000,000), and the number of cities along the
route (an integer in the range 1..100). The second line contains a
list of the cities in order along the route. Each city is identified
by an integer in the range 1..1000. Note that the cost of an
itinerary can easily add up to more than can fit into a 32-bit
integer, so you should probably use 64-bit integers (e.g., "long long"
integers in C/C++).
输出描述
Output the minimum cost of an itinerary that Bessie can use to travel
from city A to city B, as well as the minimum number of individual
flights required to achieve this minimum cost. If there is no
solution, output "-1 -1" (quotes for clarity) on a single line.
示例1
输入:
3 4 3 3 5 1 2 3 4 5 2 3 3 5 4 1 2 1 5
输出:
2 2
C++11(clang++ 3.9) 解法, 执行用时: 33ms, 内存消耗: 12280K, 提交时间: 2020-09-12 10:52:28
#include<bits/stdc++.h>
#define inf 10000000000000000
#define maxn 1010
using namespace std;
int b[maxn][maxn],d[maxn],q[maxn],c[maxn];
long long dis[maxn],a[maxn][maxn];
bool vis[maxn];
int n,m,num,s,t,mx;
inline int read() {
int x=0,f=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
void spfa() {
for(int i=1;i<=mx;i++) dis[i]=inf;
dis[s]=0; d[s]=0;
int l=0,r=1;
q[1]=s; vis[s]=1;
while(l!=r) {
l++;
if(l==maxn) l=0;
int x=q[l];
for(int i=1;i<=mx;i++)
if(dis[x]+a[x][i]<dis[i]||(dis[x]+a[x][i]==dis[i]&&d[x]+b[x][i]<d[i])) {
dis[i]=dis[x]+a[x][i];
d[i]=d[x]+b[x][i];
if(!vis[i]) {
r++;
if(r==maxn) r=0;
q[r]=i; vis[i]=1;
}
}
vis[x]=0;
}
}
int main() {
for (int i=1;i<=1000;i++)
for (int j=1;j<=1000;j++) a[i][j]=inf;
s=read(); t=read(); n=read();
for(int i=1;i<=n;i++) {
int len=read(),cnt=read();
for(int j=1;j<=cnt;j++) {c[j]=read(); mx=max(mx,c[j]);}
for(int j=1;j<cnt;j++)
for(int k=j+1;k<=cnt;k++)
if(len<a[c[j]][c[k]]||(len==a[c[j]][c[k]]&&k-j<b[c[j]][c[k]])) {
a[c[j]][c[k]]=len;
b[c[j]][c[k]]=k-j;
}
}
spfa();
if(dis[t]!=inf) printf("%lld %d",dis[t],d[t]);
else printf("-1 -1");
return 0;
}
C++14(g++5.4) 解法, 执行用时: 41ms, 内存消耗: 12428K, 提交时间: 2020-09-23 19:13:03
#include<cmath>
#include<cstdio>
#include<cstring>
#include<memory.h>
#include<iostream>
#include<algorithm>
using namespace std;
int A,B,T,t,i,j,k,n,a[101],h[1001][1001];
long long value,f[1001][1001],dis[1001],sum[1001],minn;
bool vis[1001];
int main()
{
scanf("%d%d%d",&A,&B,&T);
memset(f,-1,sizeof(f));
for(t=1;t<=T;t++)
{
scanf("%lld%d",&value,&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if (f[a[i]][a[j]]==-1||f[a[i]][a[j]]>=value)
{
if (f[a[i]][a[j]]==value)
h[a[i]][a[j]]=min(h[a[i]][a[j]],j-i);
else
h[a[i]][a[j]]=j-i;
f[a[i]][a[j]]=value;
}
}
memset(dis,127,sizeof(dis));
vis[A]=true;dis[A]=0;
for(j=1;j<1000;j++){
for(i=1;i<=1000;i++)
if (f[A][i]!=-1)
if(dis[i]>=dis[A]+f[A][i])
{
if (dis[i]==dis[A]+f[A][i])
sum[i]=min(sum[i],sum[A]+h[A][i]);
else
sum[i]=sum[A]+h[A][i];
dis[i]=dis[A]+f[A][i];
}
minn=1e12;k=0;
for(i=1;i<=1000;i++)
if(dis[i]<minn&&vis[i]==false)
k=i,minn=dis[i];
A=k;vis[k]=true;
if (k==B||k==0) break;
}
if (sum[B]!=0)
printf("%lld %d\n",dis[B],sum[B]);
else
printf("-1 -1\n");
}