lightoj1019

maksyuki 发表于 oj 分类，标签: 图论-最短路

27 8月 2015

1019 - Brush (V)

The city they live in is divided by some junctions. The junctions are connected by two way roads. They live in different junctions. And they can go to one junction to other by using the roads only.Tanvir returned home from the contest and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found that there is no brush in him room. So, he called Atiq to get a brush. But as usual Atiq refused to come. So, Tanvir decided to go to Atiq's house.

Now you are given the map of the city and the distances of the roads. You have to find the minimum distance Tanvir has to travel to reach Atiq's house.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a blank line. The next line contains two integers N (2 ≤ N ≤ 100) and M (0 ≤ M ≤ 1000), means that there are N junctions and M two way roads. Each of the next Mlines will contain three integers u v w (1 ≤ u, v ≤ N, w ≤ 1000), it means that there is a road between junction u and v and the distance is w. You can assume that Tanvir lives in the 1^stjunction and Atiq lives in the N^th junction. There can be multiple roads between same pair of junctions.

Output

For each case print the case number and the minimum distance Tanvir has to travel to reach Atiq's house. If it's impossible, then print 'Impossible'.

Sample Input

Output for Sample Input

23 21 2 50

2 3 10

3 1

1 2 40

Case 1: 60Case 2: Impossible

题目类型：单源最短路(Bellman-ford)

算法分析：直接使用Bellman-ford算法迭代求解即可，注意对于无向图来说要将无向图看作(u,v),(v,u)同属于边集E的有向图

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 1666;

struct Node
{
    int u, v, w;
};

Node edge[maxn*2];
int dis[maxn];
int n, m, len;


void bellman_ford (int s)
{
    int i;
    for (i = 1; i <= n; i++)
    {
        dis[i] = INF;
    }

    dis[s] = 0;

    for (i = 1; i < n; i++)
    {
        int j;
        for (j = 0; j < len; j++)
        {
            if (dis[edge[j].u] < INF)
            {
                dis[edge[j].v] = min (dis[edge[j].v], dis[edge[j].u] + edge[j].w);
            }
        }
    }
}

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        cin >> n >> m;

        int i, temp_u, temp_v, temp_w;
        len = 0;

        for (i = 0; i < m; i++)
        {
            cin >> temp_u >> temp_v >> temp_w;
            edge[len].u = temp_u, edge[len].v = temp_v, edge[len].w = temp_w;
            len++;
            edge[len].u = temp_v, edge[len].v = temp_u, edge[len].w = temp_w;
            len++;
        }

        bellman_ford (1);

        if (dis[n] == INF)
            cout << "Impossible" << endl;

        else
            cout << dis[n] << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1666;

struct Node

{

int u, v, w;

};

Node edge[maxn*2];

int dis[maxn];

int n, m, len;

void bellman_ford (int s)

{

int i;

for (i = 1; i <= n; i++)

{

dis[i] = INF;

}

dis[s] = 0;

for (i = 1; i < n; i++)

{

int j;

for (j = 0; j < len; j++)

{

if (dis[edge[j].u] < INF)

{

dis[edge[j].v] = min (dis[edge[j].v], dis[edge[j].u] + edge[j].w);

}

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

cin >> n >> m;

int i, temp_u, temp_v, temp_w;

len = 0;

for (i = 0; i < m; i++)

{

cin >> temp_u >> temp_v >> temp_w;

edge[len].u = temp_u, edge[len].v = temp_v, edge[len].w = temp_w;

len++;

edge[len].u = temp_v, edge[len].v = temp_u, edge[len].w = temp_w;

len++;

}

bellman_ford (1);

if (dis[n] == INF)

cout << "Impossible" << endl;

else

cout << dis[n] << endl;

}

return 0;

}

lightoj1016

lightoj1020

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

lightoj1019

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论