列表

详情

NC24164. [USACO 2015 Jan B]Cow Routing II

描述

Tired of the cold winter weather on her farm, Bessie the cow plans to fly to a warmer destination for vacation. Unfortunately, she discovers that only one airline, Air Bovinia, is willing to sell tickets to cows, and that these tickets are somewhat complicated in structure. 
Air Bovinia owns N planes (1 <= N <= 500), each of which flies on a specific "route" consisting of two or more cities. For example, one plane might fly on a route that starts at city 1, then flies to city 5, then flies to city 2, and then finally flies to city 8. No city appears multiple times in a route. If Bessie chooses to utilize a route, she can board at any city along the route and then disembark at any city later along the route. She does not need to board at the first city or disembark at the last city. Each route has a certain cost, which Bessie must pay if she uses any part of the route, irrespective of the number of cities she visits along the route, and Bessie may make use of a route only once (that is, she cannot use a route and then later use a different part of the same route). 
Bessie would like to find the cheapest way to travel from her farm (in city A) to her tropical destination (city B). Since she does not want to be confused by a complicated itinerary, she wants to use at most two routes. Please help her decide what is the minimum cost she must pay. 
[Note that the only difference between this problem and the preceding bronze problem is that here Bessie can use up to two routes, versus only one route in the preceding problem]

输入描述

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..1000), and the number of cities along the route (an
integer in the range 1..500).  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..10,000.

输出描述

Output the minimum cost of an itinerary using at most two routes that
Bessie can use to travel from city A to city B.  If there is no such
solution, output -1.

示例1

输入: 

1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 2

输出: 

7

说明:

Use route 2 to travel from city 1 to city 3, then route 1 to travel
from city 3 to city 2.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 54ms, 内存消耗: 784K, 提交时间: 2020-09-12 11:29:32 

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 7;
const int INF = 0x3f3f3f3f;
int n, x[MAXN];
vector<pair<int, int> > G[MAXN];
void solve() {
    int a, b, m;
    cin >> a >> b >> m;
    for (int i = 1; i <= m; i++) {
        int z, k;
        cin >> z >> k;
        for (int j = 0; j < k; j++) {
            cin >> x[j];
            n = max(n, x[j]);
        }
        for (int s = 0; s < k; s++) {
            for (int t = s + 1; t < k; t++) {
                if (x[s] != a && x[t] != b) continue;
                G[x[s]].push_back(make_pair(x[t], z));
            }
        }
    }
    if (a == b) {
        cout << 0 << endl;
        return;
    }
    int ret = INF;
    for (int i = 0; i < G[a].size(); i++) {
        int x = G[a][i].first; // a->x->b
        if (x == b) ret = min(ret, G[a][i].second);
        for (int j = 0; j < G[x].size(); j++) {
            if (G[x][j].first == b) {
                ret = min(ret, G[a][i].second + G[x][j].second);
            }
        }
    }
    cout << (ret == INF ? -1 : ret) << endl;
}
int main() {
    solve();
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 14ms, 内存消耗: 1016K, 提交时间: 2020-09-19 12:24:24 

#include<bits/stdc++.h>
using namespace std;
int sx[10010],ex[10010],tmp[510];
int main()
{
	int a,b,n,r=9999;
	for(int i=0;i<10010;++i)
	sx[i]=ex[i]=9999;
	scanf("%d%d%d",&a,&b,&n);
	for(int i=0;i<n;++i)
	{
		int x,y,z;
		scanf("%d%d",&x,&y);
		bool s=false;
		for(int j=0;j<y;++j)
		{
			scanf("%d",&z);
			tmp[j]=z;
			if(z==a)
			s=true;
			if(s)
			sx[z]=min(sx[z],x);
			if(s&&z==b)
			r=min(r,x);
		}
		s=false;
		for(int j=y-1;j>=0;--j)
		{
			if(tmp[j]==b)
			s=true;
			if(s)
			ex[tmp[j]]=min(ex[tmp[j]],x);
		}
	}
	for(int i=0;i<10010;++i)
	{
		if(i!=a&&i!=b&&sx[i]!=9999&&ex[i]!=9999)
		{
			r=min(r,sx[i]+ex[i]);
		}
	}
	if(r==9999)
	r=-1;
	printf("%d\n",r);
}

上一题

© 2024 nowcoder.com