哪里做网站域名不用备案,百度教育官网登录入口,海口网站关键词优化,企业网站建设一条龙全包Party
jzoj 1328
题目大意
有一个有向图#xff0c;给你一个x#xff0c;让你求每一个点到x再回去的最短路径#xff0c;输出所有最短路径的最大值
输入样例
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3输出样例
10
样例解释 数据范围 1⩽x⩽N⩽10001\le…Party
jzoj 1328
题目大意
有一个有向图给你一个x让你求每一个点到x再回去的最短路径输出所有最短路径的最大值
输入样例
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3输出样例
10
样例解释 数据范围
1⩽x⩽N⩽10001\leqslant x\leqslant N\leqslant 10001⩽x⩽N⩽1000 1⩽m⩽1000001\leqslant m\leqslant 1000001⩽m⩽100000 1⩽ti⩽1001\leqslant t_i\leqslant 1001⩽ti⩽100
解题思路
每一条边建一条正边一条反边从x跑两遍spfa然后合在一起即可
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n, m, s, x, y, z, w, h, ans, tot, p[1500], b[1500], bb[1500], head[1500], headd[1500];
struct rec
{int to, l, next;
}a[100500], e[100500];
void add(int x, int y, int z)
{a[tot].to y;a[tot].l z;a[tot].next head[x];head[x] tot;e[w].to x;//反边e[w].l z;e[w].next headd[y];headd[y] w;
}
void spfa()
{memset(b, 127/3, sizeof(b));queueintd;d.push(s);p[s] 1;b[s] 0;while(!d.empty())//最短路{h d.front();d.pop();for (int i head[h]; i; i a[i].next)if (b[h] a[i].l b[a[i].to]){b[a[i].to] b[h] a[i].l;if (!p[a[i].to]){p[a[i].to] 1;d.push(a[i].to); }} p[h] 0;} memset(bb, 127/3, sizeof(bb));d.push(s);p[s] 1;bb[s] 0;while(!d.empty())//反的最短路{h d.front();d.pop();for (int i headd[h]; i; i e[i].next)if (bb[h] e[i].l bb[e[i].to]){bb[e[i].to] bb[h] e[i].l;if (!p[e[i].to]){p[e[i].to] 1;d.push(e[i].to); }} p[h] 0;} return;
}
int main()
{scanf(%d %d %d, n, m, s);for (int i 1; i m; i){scanf(%d %d %d, x, y, z);add(x, y, z);} spfa();for (int i 1; i n; i)ans max(ans, b[i] bb[i]);//合在一起printf(%d, ans);return 0;
}
