最短路：
    [cpp] view plaincopyprint
    01.#include <set>
    02.#include <map>
    03.#include <stack>
    04.#include <cmath>
    05.#include <queue>
    06.#include <cstdio>
    07.#include <string>
    08.#include <vector>
    09.#include <iomanip>
    10.#include <cstring>
    11.#include <iostream>
    12.#include <algorithm>
    13.#define Max 2505
    14.#define FI first
    15.#define SE second
    16.#define ll long long
    17.#define PI acos（-1.0）
    18.#define inf 0x3fffffff
    19.#define LL（x） （ x 《 1 ）
    20.#define bug puts（"here"）
    21.#define PII pair<int,int>
    22.#define RR（x） （ x 《 1 | 1 ）
    23.#define mp（a,b） make_pair（a,b）
    24.#define mem（a,b） memset（a,b,sizeof（a））
    25.#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
    26.
    27.using namespace std ;
    28.
    29.#define N 1111
    30.vector<PII> G[N] ;
    31.int dis[N] , vis[N] ;
    32.int n , m ;
    33.queue<int>qe ;
    34.int cnt[N] ;
    35.void spfa（） {
    36.    while（！qe.empty（））qe.pop（） ;
    37.    for （int i = 1 ; i <= n ; i ++ ）dis[i] = inf , vis[i] = 1 , qe.push（i） ;
    38.    mem（cnt ,0） ;
    39.    while（！qe.empty（）） {
    40.        int tp = qe.front（） ;
    41.        qe.pop（） ;
    42.        vis[tp] = 0 ;
    43.        if（cnt[tp] > n） {
    44.            puts（"Impossible."） ;
    45.            return ;
    46.        }
    47.        int sz = G[tp].size（） ;
    48.        for （int i = 0 ; i < sz ; i ++ ） {
    49.            int e = G[tp][i].FI ;
    50.            int l = G[tp][i].SE ;
    51.            if（dis[e] > dis[tp] + l） {
    52.                dis[e] = dis[tp] + l ;
    53.                if（！vis[e]） {
    54.                    vis[e] = 1 ;
    55.                    qe.push（e） ;
    56.
    57.                    cnt[e] ++ ;
    58.                }
    59.            }
    60.        }
    61.    }
    62.    int mx = inf ;
    63.    for （int i = 1 ; i <= n ; i ++ ）{
    64.        mx = min（dis[i] , mx） ;
    65.//        if（dis[i] >= 1000000）{
    66.//            puts（"Impossible."）；return ;
    67.//        }
    68.    }
    69.    for （int i = 1 ; i <= n ; i ++ ）{
    70.        dis[i] -= mx - 1 ;
    71.    }
    72.    for （int i = 1 ; i <= n ; i ++ ）{
    73.        if（dis[i] >= 1000000）{
    74.            puts（"Impossible."） ; return ;
    75.        }
    76.    }
    77.    for （int i = 1 ; i < n ; i ++ ）printf（"%d ",dis[i]） ;
    78.    cout 《 dis[n] 《 endl;
    79.}
    80.char a[1111][111] ;
    81.int main（） {
    82.    while（cin 》 n , n） {
    83.        for （int i = 1 ; i <= n ; i ++ ）G[i].clear（） ;
    84.        cin 》 m ;
    85.        int s , e , l ;
    86.        for （int i = 0 ; i < m ; i ++ ） {
    87.            scanf（"%s %d %s %s",a , &s , a , a ） ;
    88.            if（a [0] == 'a'）{
    89.                scanf（"%s %d %s %s %s %s %d",a ,&l ,a ,a ,a ,a ,&e） ;
    90.//                G[e].push_back（mp（s , l）） ;
    91.                G[s].push_back（mp（e , -l）） ;
    92.            }
    93.            else {
    94.                scanf（"%d %s %s %s %s %s %s %s %d",&l ,a ,a ,a ,a ,a ,a ,a , &e） ;
    95.//                G[e].push_back（mp（s, 0）） ;
    96.//                G[s].push_back（mp（e, -l）） ;
    97.                G[e].push_back（mp（s , l）） ;
    98.                G[s].push_back（mp（e , 0）） ;
    99.            }
    100.        }
    101.        spfa（） ;
    102.    }
    103.    return 0 ;
    104.}