Jisuanke — 16959,18521

Posted by WildCow on October 15, 2018

Our Journey of Dalian Ends

Time Limit: 4000MS
Memory Limit: 131072K

Description

Life is a journey, and the road we travel has twists and turns, which sometimes lead us to unexpected places and unexpected people.

Now our journey of Dalian ends. To be carefully considered are the following questions.

Next month in Xian, an essential lesson which we must be present had been scheduled.

But before the lesson, we need to attend a wedding in Shanghai.

We are not willing to pass through a city twice.

All available expressways between cities are known.

What we require is the shortest path, from Dalian to Xian, passing through Shanghai.

Here we go.

Input

There are several test cases.

The first line of input contains an integer tt which is the total number of test cases.

For each test case, the first line contains an integer $m (m≤10000) $ which is the number of known expressways.

Each of the following mm lines describes an expressway which contains two string indicating the names of two cities and an integer indicating the length of the expressway.

The expressway connects two given cities and it is bidirectional.

Output

For each test case, output the shortest path from Dalian to Xian, passing through Shanghai, or output -1−1 if it does not exist.

Sample Input

3
2
Dalian Shanghai 3
Shanghai Xian 4
5
Dalian Shanghai 7
Shanghai Nanjing 1
Dalian Nanjing 3
Nanjing Xian 5
Shanghai Xian 8
3
Dalian Nanjing 6
Shanghai Nanjing 7
Nanjing Xian 8

Sample Output

7
12
-1


Our Journey of Xian Ends

Time Limit: 4000MS
Memory Limit: 262144K

Description

Life is a journey, and the road we travel has twists and turns, which sometimes lead us to unexpected places and unexpected people. Now our journey of Xian ends. To be carefully considered are the following questions.

A few months later in Qingdao, an essential ACM competition had been scheduled. But before the competition, we need to attend a wedding in Shanghai. And after the competition, we will leave the country from Shanghai, so Pudong International Airport ((Pudong in short)) is the end of our tour.

Here we have some vital information and missions we have to accomplish.

We have a VIP card of CNAC. For each airport we can enjoy the special VIP services in the departure floor and the arrival floor once respectively. For the pleasure of traveling, it is intolerant without VIP services. That is say that for each airport we can leave from it only once, but without regard to the last flight leaving the country from Pudong, Shanghai. Meanwhile, for each airport we can arrive at it only once.

All as we know, Shanghai has two airports, Hongqiao Airport (Hongqiao in short) and Pudong. Arriving at one and then leaving from another one is a spurned thing. But fortunately there is a nice and evil compensation service. Having a pair of transfer records between Hongqiao and Pudong in both directions, we can obtain a sensible compensation. Actually, we only consider planes in our tour, with the only exception in Shanghai. The exception is that we can arrive and leave Shanghai at different airports. However, if we decide so the compensation described above is necessary. Before the end of our tour, we will pass through Shanghai twice, once for the wedding and another time for the final departure. If we want to obtain the compensation, in the first time we must transfer from Pudong to Hongqiao, and in the second time we will transfer from Hongqiao to Pudong.

Similar transfers between airports in other city are not allowed. If we arrived at a city, we would not go to an airport in an adjacent city by car, bus or interurban railway as well.

Now, all available flights between airports are known. We have plenty of time yet. So we do not have any restriction about the number of times. What we require is the smallest total cost of flights throughout the whole tour.

Here we go.

Input

There are several test cases. The first line of input contains an integer $t (1 ≤ t ≤ 160)$ which is the total number of test cases. For each test case, the first line contains an integer m (m ≤ 10000) which is the number of known flights. Each of the following m lines describes a flight which contains two string indicating the names of two airports and an integer between 1 and 255 indicating the cost. The flight connects two given airports and it is bidirectional. The name of each airport is an non-empty string with English letters that are no longer than 10. We use “Xian” to present the only airport in Xian, and use “Qingdao” to present the only airport in Qingdao. The airports in Shanghai are described as “Hongqiao” and “Pudong” respectively.

Output

For each test case, output the smallest total cost, or output −1 if it is impossible.

Sample Input

3
4
Xian Hongqiao 3
Xian Pudong 4
Qingdao Hongqiao 4
Qingdao Pudong 3
4
Xian Hongqiao 4
Xian Pudong 3
Qingdao Hongqiao 3
Qingdao Pudong 4
6
Xian Hongqiao 4
Xian Pudong 3
Qingdao Hongqiao 3
Qingdao Pudong 4
Qingdao Xuzhou 1
Xuzhou Hongqiao 1

Sample Output

10
9
8


16959

询问从 A 到 C 的最短路,途中必须经过 B
每个点只能经过一次
如果直接先跑 A 到 B 的最短路,再跑 B 到 C 的最短路
可能重复走点
那么我们换一个思路
把 B 当作起点连 S
A C 分别连 T
求从 B 到 A 以及 B 到 C 的最小权和不相交路径
那就是一个裸的费用流了
感觉以后双向边都建 4 条边吧


18521

你要从 A 到 C 或 D,然后 从 C 或 D 到 B 最后再从 B 到 D
然后 C D 之间有一条路相连
这条路必须来回走一次或者 0 次
同时所有点只能到达一次
那么和上一题一样
我们要把 C D 当作起点
关于 C D 之间的道路思考一下我们就会发现

  • 如果我们第一次先到 C 了
    那么我们一定不能直接从 C 到 D 再从 D 出发
    因为你最后还要从 D 到 C 走一次
    这个时候我们会发现 C 要被经过两次
    D 要在最后回来的时候被经过一次
  • 如果我们第一次到 D 了
    那么我们一定要先从 D 到 C 然后回到 C 再到 D
    因为 D 不能再被到达
    然后 C 还是要被经过两次
    D 要被经过一次

那么这个时候有一个显而易见的错误建图是
S 连 D 容量为 3
D 连 C 容量为 2
D 自身拆点容量为 3
C 自身拆点容量为 2
这样的问题是
跑最大流的时候
有可能 D 往 C 流了 1 流
另外 2 流到其他边去了
而我们会发现 C 必须得到 2 流
所以我们直接 S 连 C 容量为 2
S 连 D 容量为 1
C 自身拆点容量为 2
所有和 C 相连的容量为 2
B 自身拆点容量为 2


16959


#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

struct Node
{
    int from;
    int to;
    int ne;
    int flow;
    int v;
};

struct Data
{
    string a;
    string b;
    int u;
    int v;
    int w;
};

Data data[N];
Node node[N * 10];
int n, m;
int ss, tt;
int ma[N];
int head[N];
int top;
/// SPFA
int dis[N];
int pre[N]; ///
int minn[N];
int mincost[N];
bool inq[N];
int Q[N * 10];
int ql, qr;
map<string, int> M;
int tot;
int maxflow;

void Add_chrome(int from, int to, int flow, int v)
{
    // printf("%d -> %d\n", from, to);
    node[top].from = from;
    node[top].to = to;
    node[top].flow = flow;
    node[top].v = v;
    node[top].ne = head[from];
    head[from] = top;
    top ++;
}

void Ini()
{
    top = 0;
    memset(head, -1, sizeof(head));
}

int Spfa()
{
    for(int i = 0; i <= tt; i ++){
        inq[i] = 0;
        dis[i] = INF;
        pre[i] = -1;
    }
    mincost[ss] = INF;
    mincost[tt] = 0;
    qr = ql = 0;
    dis[ss] = 0;
    minn[ss] = INF;
    inq[ss] = true;
    Q[qr] = ss;
    qr ++;
    while(ql != qr){
        int now;

        /// cout << 12312312312 << endl;
        now = Q[ql];
        // printf("now = %d\n", now);
        ql ++;
        inq[now] = false;
        for(int i = head[now]; i != -1; i = node[i].ne){
            int v;
    
            /// cout << 123123 << endl;
            v = node[i].to;
            if(node[i].flow > 0 && dis[v] > dis[now] + node[i].v){
                dis[v] = dis[now] + node[i].v;
                pre[v] = i; /// amazing  直接存边的编号
                /// pre[v] = u;
                mincost[v] = min(mincost[now], node[i].flow);
                if(!inq[v]){
                    inq[v] = true;
                    Q[qr] = v;
                    qr ++;
                }
            }
        }
    }
    
    return mincost[tt];
}

int Mincostmaxflow()
{
    int ans;
    int t;

    ans = 0;
    while(true){
        t = Spfa();
        if(!t){
            break;
        }
        maxflow += t;
        /// cout << 666 << endl;
        for(int i = pre[tt]; i != -1; i = pre[node[i].from]){
            // printf("v = %d %d\n", node[i].v, t);
            ans += t * node[i].v;
            node[i].flow -= t;
            node[i ^ 1].flow += t;
        }
    }
    
    return ans;
}

int main(int argc, char const *argv[])
{
    int ncase;
    int ans1;
    string strs, strt1, strt2;

    strs = "Shanghai";
    strt1 = "Dalian";
    strt2 = "Xian";
    cin >> ncase;
    while(ncase --){
        M.clear();
        Ini();
        tot = 1;
        maxflow = 0;
        M[strs] = tot;
        tot ++;
        M[strt1] = tot;
        tot ++;
        M[strt2] = tot;
        tot ++;
        cin >> n;
        for(int i = 0; i < n; i ++){
            cin >> data[i].a >> data[i].b >> data[i].w;
            if(!M[data[i].a]){
                M[data[i].a] = tot;
                tot ++;
            }
            if(!M[data[i].b]){
                M[data[i].b] = tot;
                tot ++;
            }
            data[i].u = M[data[i].a];
            data[i].v = M[data[i].b];
        }
        tot --;
        // printf("tot = %d\n", tot);
        Add_chrome(1, 1 + tot, 2, 0);
        Add_chrome(1 + tot, 1, 0, 0);
        for(int i = 2; i <= tot; i ++){
            Add_chrome(i, i + tot, 1, 0);
            Add_chrome(i + tot, i, 0, 0);
        }
        for(int i = 0; i < n; i ++){
            int u, v, w;
    
            u = data[i].u;
            v = data[i].v;
            w = data[i].w;
            // printf("%d %d %d\n", u, v, w);
            Add_chrome(u + tot, v, 1, w);
            Add_chrome(v, u + tot, 0, -w);
            Add_chrome(v + tot, u, 1, w);
            Add_chrome(u, v + tot, 0, -w);
        }
        ss = tot * 2 + 1;
        tt = ss + 1;
        Add_chrome(ss, M[strs], 2, 0);
        Add_chrome(M[strs], ss, 0, 0);
        Add_chrome(M[strt1] + tot, tt, 1, 0);
        Add_chrome(tt, M[strt1] + tot, 0, 0);
        Add_chrome(M[strt2] + tot, tt, 1, 0);
        Add_chrome(tt, M[strt2] + tot, 0, 0);
//        for(map<string, int>::iterator it = M.begin(); it != M.end(); it ++){
//            cout << it -> first << ' ' << it -> second << endl;
//        }
        ans1 = Mincostmaxflow();
        // printf("%d %d\n", maxflow, ans1);
        if(maxflow == 2){
            printf("%d\n", ans1);
        }
        else{
            printf("-1\n");
        }
    }

    return 0;
}

16959


#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

struct Node
{
    int from;
    int to;
    int ne;
    int flow;
    int v;
};

struct Data
{
    string a;
    string b;
    int u;
    int v;
    int w;
};

Data data[N];
Node node[N * 10];
int n, m;
int ss, tt;
int ma[N];
int head[N];
int top;
/// SPFA
int dis[N];
int pre[N]; ///
int minn[N];
int mincost[N];
bool inq[N];
int Q[N * 10];
int ql, qr;
map<string, int> M;
int tot;
int maxflow;

void Add_chrome(int from, int to, int flow, int v)
{
    // printf("%d -> %d\n", from, to);
    node[top].from = from;
    node[top].to = to;
    node[top].flow = flow;
    node[top].v = v;
    node[top].ne = head[from];
    head[from] = top;
    top ++;
}

void Ini()
{
    top = 0;
    memset(head, -1, sizeof(head));
}

int Spfa()
{
    for(int i = 0; i <= tt; i ++){
        inq[i] = 0;
        dis[i] = INF;
        pre[i] = -1;
    }
    mincost[ss] = INF;
    mincost[tt] = 0;
    qr = ql = 0;
    dis[ss] = 0;
    minn[ss] = INF;
    inq[ss] = true;
    Q[qr] = ss;
    qr ++;
    while(ql != qr){
        int now;

        /// cout << 12312312312 << endl;
        now = Q[ql];
        // printf("now = %d\n", now);
        ql ++;
        inq[now] = false;
        for(int i = head[now]; i != -1; i = node[i].ne){
            int v;
    
            /// cout << 123123 << endl;
            v = node[i].to;
            if(node[i].flow > 0 && dis[v] > dis[now] + node[i].v){
                dis[v] = dis[now] + node[i].v;
                pre[v] = i; /// amazing  直接存边的编号
                /// pre[v] = u;
                mincost[v] = min(mincost[now], node[i].flow);
                if(!inq[v]){
                    inq[v] = true;
                    Q[qr] = v;
                    qr ++;
                }
            }
        }
    }
    
    return mincost[tt];
}

int Mincostmaxflow()
{
    int ans;
    int t;

    ans = 0;
    while(true){
        t = Spfa();
        if(!t){
            break;
        }
        maxflow += t;
        /// cout << 666 << endl;
        for(int i = pre[tt]; i != -1; i = pre[node[i].from]){
            // printf("v = %d %d\n", node[i].v, t);
            ans += t * node[i].v;
            node[i].flow -= t;
            node[i ^ 1].flow += t;
        }
    }
    
    return ans;
}

int main(int argc, char const *argv[])
{
    int ncase;
    int ans1;
    string str1, str2, str3, str4;

    str1 = "Pudong";
    str2 = "Hongqiao";
    str3 = "Xian";
    str4 = "Qingdao";
    cin >> ncase;
    while(ncase --){
        M.clear();
        Ini();
        tot = 1;
        maxflow = 0;
        M[str1] = tot;
        tot ++;
        M[str2] = tot;
        tot ++;
        M[str3] = tot;
        tot ++;
        M[str4] = tot;
        tot ++;
        cin >> n;
        for(int i = 0; i < n; i ++){
            cin >> data[i].a >> data[i].b >> data[i].w;
            if(!M[data[i].a]){
                M[data[i].a] = tot;
                tot ++;
            }
            if(!M[data[i].b]){
                M[data[i].b] = tot;
                tot ++;
            }
            data[i].u = M[data[i].a];
            data[i].v = M[data[i].b];
        }
        tot --;
        // printf("tot = %d\n", tot);
        Add_chrome(1, 1 + tot, 1, 0);   /// P -> P
        Add_chrome(1 + tot, 1, 0, 0);
        Add_chrome(2, 2 + tot, 2, 0);   /// H -> H
        Add_chrome(2 + tot, 2, 0, 0);
//        Add_chrome(1 + tot, 2, 2, 0);   /// P -> H
//        Add_chrome(2, 1 + tot, 0, 0);
        Add_chrome(4, 4 + tot, 2, 0);   /// Q -> Q
        Add_chrome(4 + tot, 4, 0, 0);
        Add_chrome(3, 3 + tot, 1, 0);   /// X -> X
        Add_chrome(3 + tot, 3, 0, 0);
        for(int i = 5; i <= tot; i ++){
            Add_chrome(i, i + tot, 1, 0);
            Add_chrome(i + tot, i, 0, 0);
        }
        for(int i = 0; i < n; i ++){
            int u, v, w;

            u = data[i].u;
            v = data[i].v;
            w = data[i].w;
            if(u == 2 || v == 2){
                Add_chrome(u + tot, v, 2, w);
                Add_chrome(v, u + tot, 0, -w);
                Add_chrome(v + tot, u, 2, w);
                Add_chrome(u, v + tot, 0, -w);
            }
            else{
                Add_chrome(u + tot, v, 1, w);
                Add_chrome(v, u + tot, 0, -w);
                Add_chrome(v + tot, u, 1, w);
                Add_chrome(u, v + tot, 0, -w);
            }
            // printf("%d %d %d\n", u, v, w);
        }
        ss = tot * 2 + 1;
        tt = ss + 1;
//        Add_chrome(ss, M[str1], 3, 0);
//        Add_chrome(M[str1], ss, 0, 0);
//        Add_chrome(M[str3] + tot, tt, 1, 0);
//        Add_chrome(tt, M[str3] + tot, 0, 0);
//        Add_chrome(M[str4] + tot, tt, 2, 0);
//        Add_chrome(tt, M[str4] + tot, 0, 0);
        Add_chrome(ss, M[str2], 2, 0);
        Add_chrome(M[str2], ss, 0, 0);
        Add_chrome(ss, M[str1], 1, 0);
        Add_chrome(M[str1], ss, 0, 0);
        Add_chrome(M[str3] + tot, tt, 1, 0);
        Add_chrome(tt, M[str3] + tot, 0, 0);
        Add_chrome(M[str4] + tot, tt, 2, 0);
        Add_chrome(tt, M[str4] + tot, 0, 0);
//        for(map<string, int>::iterator it = M.begin(); it != M.end(); it ++){
//            cout << it -> first << ' ' << it -> second << endl;
//        }
        ans1 = Mincostmaxflow();
        /// printf("%d %d\n", maxflow, ans1);
        if(maxflow == 3){
            printf("%d\n", ans1);
        }
        else{
            printf("-1\n");
        }
    }

    return 0;
}