최 단 로 - 체인 식 전진 성, 디 제 스 트 라 알고리즘 의 전형 적 인 예제

 
    

      3 30 1 10 2 31 2 10 23 10 1 11 2 
    
 
   

 
    

      2-1 
    
 
   

//   ——     ，    
#include 
#define mp make_pair
using namespace std;

const int MAXN = (int)207;
const int MAXM = (int)1e3+7;
const int INF = (int)0x3f3f3f3f;
typedef pair pi;
int Head[MAXN];
int dis[MAXN];
int cnt,N,M;

struct Node{
    int next;
    int to;
    int w;
}edge[MAXM];

void emp(){
    memset(Head,-1,sizeof(Head));
    memset(dis,0x3f,sizeof(dis));
    cnt = 0;
}

void Add(int x,int y,int w){
    edge[cnt].next = Head[x];
    edge[cnt].to = y;
    edge[cnt].w = w;
    Head[x] = cnt;
    cnt ++;
}

void show(){
    int i,t;
    for(i = 1;i <= N;i ++){
        t = Head[i];
        while(~t){
            cout << i << "-->" << edge[t].to << " need " << edge[t].w << endl;
            t = edge[t].next;
        }
    }
}

int main()
{
    while (cin >> N >> M){
        emp();

        int x,y,w;
        for (int i = 0;i < M;i ++){
            cin >> x >> y >> w;
            Add(x,y,w);
            Add(y,x,w);
        }

        int s,t;
        cin >> s >> t;

        priority_queue  Q;
        Q.push(mp(0,s));
        dis[s] = 0;

        while (!Q.empty()){
            int k = Q.top().second;
            Q.pop();

            for (int i = Head[k]; ~i;i = edge[i].next){
                if (dis[edge[i].to] > dis[k] + edge[i].w){
                    dis[edge[i].to] = dis[k] + edge[i].w;
                    Q.push(mp(-dis[edge[i].to],edge[i].to));
                }
            }
        }
        if (dis[t] != INF) cout << dis[t] << endl;
        else cout << -1 << endl;

        show();
    }
}
//                    hdu1874     。