问题 A: 最短路径迪杰斯特拉算法入门
时间限制: 1 Sec 内存限制: 128 MB
提交: 242 解决: 204
[提交][状态][讨论版][命题人:quanxing][Edit] [TestData]
题目链接:http://acm.ocrosoft.com/problem.php?cid=1712&pid=0
题目描述
如图,求最短路径。
输入
顶点数n 边数m
m条边的顶点和权值
某两个顶点
输出
顶点0到每个顶点的最短路径
样例输入
6 9
0 2 5
0 3 30
1 0 2
1 4 8
2 1 15
2 5 7
4 3 4
5 3 10
5 4 18
0 4
样例输出
28
思路:
裸的dijstra,没什么思路,主要在dijstra怎么写
代码:
#include<bits/stdc++.h>
using namespace std;
int n, m, pos;
#define inf 0x3f3f3f3f
#define maxn 105
int visit[maxn], dis[maxn], length[maxn][maxn];
int Start, End;
int dijstra()//迪杰斯特拉算法
{
for (int i = 0; i < n; i++)
{
dis[i] = length[Start][i];//初始化
}
dis[Start] = 0;
visit[Start] = 1;
for (int i = 1; i < n; i++)//依次挑最短的边去动态规划
{
int min = inf;
for (int j = 0; j < n; j++)
{
if (visit[j] == 0 && min > dis[j])//标记最短的点
{
min = dis[j];
pos = j;//记录那个点
}
}
visit[pos] = 1;
for (int j = 0; j < n; j++)
{
if (visit[j] == 0 && dis[j] > dis[pos] + length[pos][j])//动态规划
{
dis[j] = dis[pos] + length[pos][j];
}
}
}
return dis[End];
}
int main()
{
cin >> n >> m;
memset(length, inf, sizeof(length));
for (int i = 1; i <= m; i++)
{
int start, end;
cin >> start >> end;
cin >> length[start][end];
//length[end][start]= length[start][end];
}
cin >> Start >> End;
cout << dijstra();
}