图结构练习——最短路径

图结构练习——最短路径

Time Limit: 1000MS Memory limit: 65536K

题目描述

 给定一个带权无向图，求节点1到节点n的最短路径。  

输入

 输入包含多组数据，格式如下。 第一行包括两个整数n m，代表节点个数和边的个数。(n<=100) 剩下m行每行3个正整数a b c，代表节点a和节点b之间有一条边，权值为c。  

输出

 每组输出占一行，仅输出从1到n的最短路径权值。（保证最短路径存在）  

示例输入

3 2 1 2 1 1 3 1 1 0

示例输出

1 0

#include <stdio.h> #include <stdlib.h> #include<queue> #define INF 0x3f3f3f3f #define MAX 100 using namespace std; typedef struct arcnode { int adj; int info; } arcnode, adjmatrix[101][101]; typedef struct { adjmatrix a; int vn; int an; } MG; struct node { int data; int step; } t, s; int k;//初始点 int i, j; int create(MG &g, int n, int m) { int v1, v2, w; g.vn = n; g.an = m; for(i=1; i<=g.vn; i++) for(j=1; j<=g.vn; j++) { if(i==j) g.a[i][j].adj = 0; else g.a[i][j].adj = INF; } for(i=1; i<=g.an; i++) { scanf("%d %d %d", &v1, &v2, &w); if(g.a[v1][v2].adj > w||g.a[v2][v1].adj > w) g.a[v1][v2].adj = w; //有重复边选权值最小的保存 g.a[v2][v1] = g.a[v1][v2]; } return 1; } int v[101];//标记数组 void floyd(MG &g)弗洛伊德算法 { int i, j, k; for(k=1; k<=g.vn; k++) for(i=1; i<=g.vn; i++) for(j=1; j<=g.vn; j++) if(i!=j) { if(g.a[i][j].adj > g.a[i][k].adj + g.a[k][j].adj) g.a[i][j].adj = g.a[i][k].adj + g.a[k][j].adj; } } int main() { MG g; int n, m; while(~scanf("%d %d", &n, &m)) { create(g, n, m); floyd(g); printf("%d\n", g.a[1][n].adj); } return 0; }