大连网站开发培训价格,网页设计在线制作,网页设计实训要求,海口建设网站的公司前言
这是一篇迟到的博客 题目
找一条最廉价的最短路径 输入输出#xff08;建议无视#xff09;
Input
输入文件第一行有两个整数m和n#xff0c;用一个空格隔开#xff0c;其中#xff0c;m是顶点数#xff0c;而n是边数。接下来的n行给出所有的边及其价值#…前言
这是一篇迟到的博客 题目
找一条最廉价的最短路径 输入输出建议无视
Input
输入文件第一行有两个整数m和n用一个空格隔开其中m是顶点数而n是边数。接下来的n行给出所有的边及其价值每行有3个整数(相邻两个整数间有一个空格)表示起点终点和边的价值。顶点最多有100个编号在0到99之间。边最多有1000条其价值在0到2^15-1之间。
Output
输出文件仅有一行包含一个整数即V0→V1的廉价最短路径的费用。当出现有多个廉价最短路径的情况时它们的费用是一样的。
Sample Input
4 5 0 2 2 0 3 2 0 1 10 2 1 2 3 1 2
Sample Output
10 解题思路
正常最短路算法只不过加上一个判断 代码
#includecstdio
using namespace std;
struct woc{long long next,x,y,w;
};
woc a[1001];
long long xx,yy,n,m,k,state[101],ls[101],t,head,tail,f[101],s[101];
bool v[101];
int main()
{scanf(%lld%lld,n,m);state[1]1;int u0;for (int i1;im;i){scanf(%lld%lld%lld,xx,yy,a[u1].w);xx;yy;a[u].nextls[xx];a[u].xxx;a[u].yyy;ls[xx]u;}for (int i1;in;i) {f[i]2147483647;s[i]2147483647;}head0;tail1;state[1]1;v[state[1]]true;f[1]0; s[1]0;while (head!tail)//SPFA{head;head(head-1)%n1;tls[state[head]];while (t!0){if (f[a[t].x]1f[a[t].y] || s[a[t].y]s[a[t].x]a[t].w f[a[t].x]1f[a[t].y]){s[a[t].y]s[a[t].x]a[t].w;//改变价值f[a[t].y]f[a[t].x]1;if (!v[a[t].y]){tail;tail(tail-1)%n1;state[tail]a[t].y;v[a[t].y]true;}}ta[t].next;}v[state[head]]false;}printf(%lld,s[2]);
}
