1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 |
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 101;
- int a[MAXN][MAXN];
- int book[MAXN];
- int dis[MAXN];
- int n, m;
- int Dijkstra(){
- for(int i = 1; i <= n; i++){
- dis[i] = a[1][i];
- book[i] = 0;
- }
- book[1] = 1;
- for(int i = 1; i < n; i++){
- int u = 2, MIN = INT_MAX;
- for(int j = 2; j <= n; j++){
- if(book[j] == 0 && dis[j] < MIN){
- u = j;
- MIN = dis[j];
- }
- }
- book[u] = 1;
- for(int j = 2; j <= n; j++){
- if(a[u][j] < INT_MAX && book[j] == 0 && dis[j] > dis[u] + a[u][j]){
- dis[j] = dis[u]+a[u][j];
- }
- }
- }
- return dis[n];
- }
- int main(){
- while(cin >> n >> m){
- if(n == 0 && m == 0)break;
- for(int i = 1; i <= n; i++){
- for(int j = 1; j <= n; j++){
- if(i != j)
- a[i][j] = INT_MAX;
- else a[i][j] = 0;
- }
- }
- for(int i = 1; i <= m; i++){
- int x, y, z;
- cin >> x >> y >> z;
- a[x][y] = a[y][x] = z;
- }
- int sum = Dijkstra();
- cout << sum << endl;
- }
- }
|