14072: 【原4072】日天卖面包

题目描述

author: MW 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4072

Description

日天想要开一家面包店，卖各种各样的面包，他决定把店开在n个城市中的1个，这些城市的编号从1到n。而这些城市之间有m条道路，每一条连接着两个城市。

为了能在面包店里烤面包，日天需要一些制造面包的原料，而这些原料只在一些城市里有。k个原料城市分别在\(a_1,a_2,\cdots,a_k, 且a_i\in [1,n]\)

然而不幸的是，当地有一个政策，面包店不能开在有原料的城市里，因此他只能将面包店开在另外的n-k个城市中。当然，原料是要有运输费用的，日天需要为每1道路长度支付1元。

更严谨的说，如果日天吧面包店开在某一个城市b\((a_i \not= b 对于任意的 1\leq i \leq k)\), 并选择了一个有原料的城市s(s \( = a_j, 对某一j,1\leq j\leq k)\)，并且b和s被一些路径连接在一起，这些路径的长度之和为x (如果有多条路径，日天可以选择他想要的那一条路径)，则日天需要支付x元。

日天想要让自己的面包店成本最低，所以需要最低的运费。

Input Format

第一行，有三个整数n, m, k，分别对应城市数，道路数和有原料城市的数量。

接下来的m行，每一行包含三个整数u, v, l (\(u\not=v\))，表示城市u和v之间有一条长度为l的道路。

如果k > 0，那么最后一行会有k个不同的整数\(a_1, a_2, \cdots, a_k\)，表示各个有原料城市的编号。如果k = 0，这一行不会出现。

Output Format

输出日天需要支付的最少的运费。

如果不存在能够开面包店的城市，则输出-1

Sample Input 1

Sample Output 1

Sample Input 2

3 1 1
1 2 3
3

Sample Output 2

-1

Limits

对于50%的数据，\(1\leq n \leq 20\)

对于100%的数据，\(1\leq n, m \leq 1e5\)

其中\(1\leq k \leq n, 1\leq l\leq 1e9\)

FineArtz's solution

/* 日天卖面包 */
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <cstring>
using namespace std;

class Point{
public:
    map<int, int> edge;
};

Point a[100005];
set<int> s;
bool is[100005];
int n, m, k;

int main(){
    cin >> n >> m >> k;
    if (k == 0){
        cout << "-1" << endl;
        return 0;
    }
    if (n >= 50){
    memset(is, 0, sizeof(is));
    for (int i = 1; i <= m; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        if (a[u].edge.find(u) == a[u].edge.end()){
            a[u].edge[v] = w;
            a[v].edge[u] = w;
        }
        else{
            if (a[u].edge[v] > w){
                a[u].edge[v] = w;
                a[v].edge[u] = w;
            }
        }
    }
    int ans = 2147483647;
    int t;
    for (int i = 1; i <= k; ++i){
        cin >> t;
        s.insert(t);
        is[t] = true;
    }
    for (auto i : s){
        for (auto j : a[i].edge){
            if (!is[j.first]){
                ans = min(ans, j.second);
            }
        }
    }
    if (ans == 2147483647)
        cout << "-1" << endl;
    else
        cout << ans << endl;
    }
    else{
        int a[25][25];
        for (int i = 0; i < 25; ++i)
            for (int j = 0; j < 25; ++j)
                a[i][j] = -1;
        for (int i = 1; i <= m; ++i){
            int u, v, w;
            cin >> u >> v >> w;
            if (a[u][v] == -1){
                a[u][v] = w;
                a[v][u] = w;
            }
            else{
                if (a[u][v] > w){
                    a[u][v] = w;
                    a[v][u] = w;
                }
            }
        }
        int s[25];
        bool is[25];
        memset(is, 0, sizeof(is));
        for (int i = 1; i <= k; ++i){
            cin >> s[i];
            is[s[i]] = true;
        }
        int ans = 2147483647;
        for (int i = 1; i <= k; ++i){
            for (int j = 1; j <= n; ++j){
                if (is[j]) continue;
                if (a[s[i]][j] == -1) continue;
                ans = min(ans, a[s[i]][j]);
            }
        }
        if (ans == 2147483647)
            cout << "-1" << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

bool city[100001] = { 0 };
int road[100000][3] = { 0 };

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &road[i][0], &road[i][1], &road[i][2]);
    }

    for (int i = 0; i < k; i++) {
        int temp;
        scanf("%d", &temp);
        city[temp] = true;
    }

    //寻找最短路
    long long minMoney=1e10;
    for (int i = 0; i < m; i++) {
        if ((city[road[i][0]] && !city[road[i][1]]) || (!city[road[i][0]] && city[road[i][1]])) {
            if (road[i][2] < minMoney)
                minMoney = road[i][2];
        }
    }

    if (k == 0 || minMoney >= 1e10)
        cout << -1;
    else
        cout << minMoney;

    return 0;
}