[最短路+水题]LightOJ 1019 - Brush (V)

求最短路。。。 要多水就有多水，刷水的感觉很差，很少用SPFA，所以算是练习下SPFA把。。

传送门：http://lightoj.com/volume_showproblem.php?problem=1019

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 111;
int inQ[MAXN],dist[MAXN],t,n,m;
vector<pair<int,int> > g[MAXN];
void init(){
    fill(dist,dist+MAXN,0x3fffffff);
    memset(inQ,0,sizeof(inQ));
    for(int i=0;i<MAXN;i++)g[i].clear();
}
int SPFA(int src,int dest){
    queue<int> Q;
    Q.push(src);
    inQ[src] = 1;
    dist[src] = 0;
    while(!Q.empty()){
        int now = Q.front();
        Q.pop();inQ[now] = 0;
        for(int i=0;i<(int)g[now].size();i++){
            //cout<<now<<" "<<v<<" "<<val[v]<<endl;
            int v = g[now][i].first,w = g[now][i].second;
            if(dist[v]>dist[now]+w){
                dist[v] = dist[now]+w;
                if(!inQ[v]){
                    inQ[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
    return dist[dest];
}
int main(){
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        scanf("%d%d",&n,&m);init();
        while(m--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            g[a].push_back(make_pair(b,c));
            g[b].push_back(make_pair(a,c));
        }
        int d = SPFA(1,n);
        if(d!=0x3fffffff)
        printf("Case %d: %d\n",cas,d);
        else
        printf("Case %d: Impossible\n",cas);
    }
    return 0;
}