zoj 3396 Conference Call

 Good News! Utopia Polycom begins to offer a whole new service, Conference Call. This new service enables three users to make phone calls at the same time and talk to each other. It's very useful when several people are discussing about one shared topic. For example, Tom, Rosemary and you plan to go picnic tomorrow. You just need to make one conference call, so that you can discuss with Tom and Rosemary simultaneously. It's extremely convenient, yes?

However, it has a lot of technological problems to start this service. It took engineers of Utopia Polycom five years to conquer all these problems. One of the biggest problem is how to make the communication line connected. To solve this problem, they have constructed a powerful net of transfer stations. Every single phone is connected to its nearest transfer station, some transfer stations are connected to each other by wires. When to make a conference call, signal will start from the dialling telphone. The signal will be transferred through transfer stations and finally reach the other two phones.

Since the distances between each two transfer stations are various, the cost for the signal to go through the wires is different as well. Assume there are n telphones(numbered from 1 to n) and m(numbered from 1 to m) transfer stations in this communication net. The total cost for a line is the sum of the costs of the wires in the line. Our problems remains, what is the minimal total cost to make a conference call among three telphone a, b and c. As showing below, the minimal total cost to make a conference call among telphone 1, 2, 3 is 12.

Input

There are multiple cases. For each test case, the first line contain three pZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc2l0aXZlIGludGVnZXJzLAo8ZW0+bjwvZW0+ICg8ZW0+bjwvZW0+IKHcIDEwMDAwKSwgPGVtPm08L2VtPiAoPGVtPm08L2VtPiCh3CA1MDApLCA8ZW0+bDwvZW0+ICg8ZW0+bDwvZW0+IKHcIDEwMDAwKS4KPGVtPmw8L2VtPiBtZWFucyB0aGUgbnVtYmVyIG9mIHdpcmVzLiBUaGVuIGZvbGxvd3MgPGVtPm48L2VtPiBsaW5lcy4gRWFjaCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyCjxlbT50PHN1Yj5pPC9zdWI+PC9lbT4gKDEgodwgPGVtPnQ8c3ViPmk8L3N1Yj48L2VtPiCh3Ao8ZW0+bTwvZW0+KSwgd2hpY2ggbWVhbnMgdGhlIG51bWJlciBvZiB0cmFuc2ZlciBzdGF0aW9uIE5vLjxlbT5pPC9lbT4gdGVscGhvbmUgaXMgY29ubmVjdGVkIHRvLiBUaGVuIGZvbGxvd3MKPGVtPmw8L2VtPiBsaW5lcywgZWFjaCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIDxlbT5hPC9lbT4sIDxlbT5iPC9lbT4sIDxlbT5DPC9lbT4gKDEgodwKPGVtPkM8L2VtPiCh3CA1MDApLCB3aGljaCBtZWFucyA8ZW0+YTwvZW0+IGFuZCA8ZW0+YjwvZW0+IHRyYW5zZmVyIHN0YXRpb25zIGFyZSBjb25uZWN0ZWQgdG8gZWFjaCBvdGhlciBieSBhIHdpcmUgd2l0aCB0aGUgYW1vdW50IG9mIGNvc3QKPGVtPkM8L2VtPi4gSWYgYSBwYWlyICg8ZW0+YTwvZW0+LCA8ZW0+YjwvZW0+KSBkb2Vzbg=="t appear in these l lines, that means tranfer stations a, b are not connected.

The next line is a single integer q (q ≤ 50). Then follow q lines. Each line contains three integers x, y, z. You are supposed to calculate the minimal total cost to make a conference call among telphone x, y, z. Each test case is seperated by a blank line. Proceed to the end of the file.

Output

For each test case i, print case number in the form "Case #i" in one single line. Then for each inquiry j, print one line in the form "Line j: " and if the conference call can be made and the minimal total cost is Min, print the sentense "The minimum cost for this line is Min." else you should print "Impossible to connect!". Look at the samples for details.

Sample Input

3 5 5
2
1
5
1 2 6
2 3 1
3 4 2
4 5 3
1 5 12
1
1 2 3

3 3 1
1
2
3
2 3 4
1
1 2 3

Sample Output

Case #1
Line 1: The minimum cost for this line is 12.
Case #2
Line 1: Impossible to connect!

題意：現在某公司推出一項新項目，支持三個人之間的電話通化，每台電話連接一個最近的中轉站，然而要進行通話，是需要在中轉站上傳輸信號，傳輸的距離越長費用就越高，求出給定的三台電話的通話所需的最短路程。

思路：使用floyd算法就出每兩個城市之間的最短路徑，然後依據這些路徑求出三台電話之間的最短路徑。求的時候還是有一個大坑的，不能只枚舉給定三個城市之間的最短路。例如：看下圖，假設求A,B,C三點的最短路，如果只涉及A，B，C三點的話，求出的路徑顯然不是最短的，假設以D為中心，求出來的路徑肯定比剛才的路徑要短。

代碼：

#include 
#include 
#include 
#define INF 100000000
using namespace std;
int root[10004];         //用來存儲每台電話最近的中轉站
int f[504][504];
int n,m,l;
void init()
{
    for(int i=0; i<=n; i++)
        for(int j=0; j<=i; j++)
        {
            if(i!=j) f[i][j]=f[j][i]=INF;
            else f[i][j]=0;
        }
}

void floyd()
{
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        if(f[i][j]>f[i][k]+f[k][j])
        {
            f[i][j]=f[i][k]+f[k][j];
        }
    }
}
int main()
{
    int ans=1;
    while(scanf("%d%d%d",&m,&n,&l)!=EOF)
    {
        init();
        for(int i=1;i<=m;i++)
        scanf("%d",&root[i]);
        int x,y,z;
        for(int i=0;iz) f[x][y]=f[y][x]=z;
        }
        floyd();
        scanf("%d",&l);
        printf("Case #%d\n",ans++);
        for(int i=1;i<=l;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            x=root[x];
            y=root[y];
            z=root[z];
            int sum=INF;
            for(int i=1;i<=n;i++)          //本題關鍵，很坑....
            {
                if(sum>f[i][x]+f[i][y]+f[i][z])
                    sum=f[i][x]+f[i][y]+f[i][z];
            }

            printf("Line %d: ",i);
            if(sum>=INF) printf("Impossible to connect!\n");
            else printf("The minimum cost for this line is %d.\n",sum);
        }
    }
    return 0;
}