SDNUOJ 1223 Tom's problem A

Description

In the future ,One day, tom feel so happy ,because he have a date with a girl,but they don’t live in the same city , so tom want you help him find the fastest way to the girl’s city,You should note that with the development of technology, transport can go beyond the speed of light, so the time you spend would be less than zero, but if you return to the past you can not have the date with the girl,there n(1<n<=100) city in this country and three are m(1<m<1000) roads in this country;

Tom in the first city,the girl in the city n;

Input

The fist line is m,n;

Next m lines is a,b,c (a,b is the name of city , c is the time you cost from city a to city b)

Output

The shortest time to reach the girl’s city

(if tom return to the past ,out IMPOSSIBLE!)

Sample Input

1 2
1 2 10
3 4
1 2 10
2 3 10
3 4 -5

Sample Output

10
IMPOSSIBLE!

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100005;
const int inf = 0x3f3f3f3f;

struct node///存放“边”
{
    int from, to, w, pre;
} a[N];

///n为点的个数，dis[i]表示从起点到点i目前最短路径
///tot为队列内元素个数，sum为队列内元素的dis[]之和
int head[N], cnt, dis[N], times[N], tot, sum, n, m;
bool vis[N];///vis[i]：0表示i不在队列里，1表示i在队列里

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
        dis[i] = inf, times[i] = 0, vis[i] = 0, head[i] = -1;
    return ;
}

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cnt++;
    a[cnt].from = to;
    a[cnt].to = from;
    a[cnt].w = w;
    a[cnt].pre = head[to];
    head[to] = cnt;
    cnt++;
}

bool spfa(int start)
{
    deque<int> q;
    dis[start] = 0;///到自己的距离为0
    vis[start] = 1;
    q.push_front(start);
    tot = 1, sum = 0;
    while(q.size())
    {
        int first = q.front();
        q.pop_front();
        vis[first] = 0;
        tot--;
        sum -= dis[first];
//        cout << "当前检测点 " << first << '\n';

        for(int i = head[first]; ~ i; i = a[i].pre)
        {
            int t = a[i].to;
//            cout << "当前检测终点 " << t << '\n';
//            cout << "从起点到此终点最短路径 " << dis[t] << '\n';
//            cout << "经由当前检测点到此终点最短路径 " << dis[first] + a[i].w << '\n';

            ///若 “起点到终点t的距离” 大于 “起点经由first点到终点t的距离”
            if(dis[t] > dis[first] + a[i].w)
            {
                dis[t] = dis[first] + a[i].w;
                if(!vis[t])
                {
                    vis[t] = 1;         ///极值优化             ///平均值优化
                    if(q.empty() || dis[t] > dis[q.front()] || dis[t] * tot >= sum)
                        q.push_back(t);
                    else
                        q.push_front(t);
                    sum += dis[t];
                    tot++;
                    if(++times[t] >= n)
                        return 0;
                }
            }
        }
    }
    return 1;
}

int main()
{
    while(~scanf("%d%d", &m, &n))
    {
        init();
        int b, c, d;
        int tem = m;
        while(tem--)
        {
            scanf("%d%d%d", &b, &c, &d);
            add(b, c, d);
        }
//        for(int i = 0; i < cnt; ++i)
//        cout << a[i].from << ' ' << a[i].to << ' ' << a[i].w << ' ' << a[i].pre << '\n';
        if(spfa(1))
            cout << dis[n] << '\n';
        else
            cout << "IMPOSSIBLE!" << '\n';
    }
    return 0;
}