sdnu1223 Tom'problem A (spfa判负环)

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!

题意模糊不清。。

目的就是判有没有负环

如果有（回到了过去）就impossible

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int dis[N],vis[N],head[N],num[N];
int n,m,tot;

struct Edge
{
    int u,v,w,next;
}edge[N];

void add(int a,int b,int c)
{
    edge[tot].u=a;
    edge[tot].v=b;
    edge[tot].w=c;
    edge[tot].next=head[a];
    head[a]=tot++;
}

bool spfa(int s)
{
    queue<int>q;
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    memset(vis,false,sizeof(vis));
    memset(num,0,sizeof(num));
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int pos=q.front();
        q.pop();
        vis[pos]=false;
        num[pos]++;
        for(int i=head[pos];i!=-1;i=edge[i].next)
        {
            if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
            {
                dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
                if(!vis[edge[i].v])
                {
                    vis[edge[i].v]=true;
                    q.push(edge[i].v);
                    if(num[edge[i].v]>=n)
                        return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    while(scanf("%d%d",&m,&n)!=EOF&&n+m)
    {
        int a,b,c;
        tot=0;
        memset(head,-1,sizeof(head));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        if(!spfa(1))
            cout<<"IMPOSSIBLE!"<<'\n';
        else
            cout<<dis[n]<<'\n';
    }
    return 0;
}