程序填空题：最短路径（分支限界法）

试实现最短路径算法。


### 输入样例：
第1行输入结点数vexnum和边数arcnum。接下来依次输入arcnum行，每行输入3个值，前两个字符表示结点编号，后一个数表示两个结点之间边的权值。最后一行输入源点编号。

```in
6 8
0 5 100
0 2 10
0 4 30
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
0
```

### 输出样例：
输出源点到终点（按终点编号递增顺序）的最短路径，无路径输出0。
```out
0
10
50
30
60
```


```c++
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f //表示∞
#define MAXN 51
int n,m; //图顶点个数和边数
int a[MAXN][MAXN]; //图的邻接矩阵
int v; //源点
int dist[MAXN]; //dist[i]源点到顶点i的最短路径长度
struct NodeType //队列结点类型
{
int vno; //顶点编号
int length; //路径长度
};

void bfs();
void dispallpath();

int main()
{
memset(dist,INF,sizeof(dist)); //初始化为∞
memset(a,INF,sizeof(a)); //初始化为∞
cin >> n>> m;
for (int i=0;i a[i][i]=0;
for(int i=0;i int x,y,w;
cin>>x>>y>>w;
a[x][y]=w;
}
cin >>v;
bfs();
dispallpath();
return 0;
}

void bfs() //求解算法
{
NodeType e,e1;
queue pqu;
e.vno=v; //建立源点结点e
e.length=0;
pqu.push(e); //源点结点e进队
dist[v]=0;
while()
{
e=pqu.front();
;
for (int j=0; j {
if()
{
dist[j]=e.length+a[e.vno][j];
e1.vno=j; //建立相邻顶点j的结点e1
e1.length=dist[j];
;
}
}
}
}

void dispallpath() //输出源点v出发的所有最短路径
{
for (int i=0;i {
if (v!=i){
if (dist[i]==INF)
printf("0\n");
else
printf("%d\n",dist[i]);
}
}
}
```






答案：
第1空：!pqu.empty()

第2空： pqu.pop()

第3空：a[e.vno][j]
第4空：pqu.push(e1)