[FJOI2007]轮状病毒

[FJOI2007]轮状病毒

Time Limit:500MS Memory Limit:165536K
Total Submit:141 Accepted:63
Case Time Limit:100MS

Description

给定n(N<=100),编程计算有多少个不同的n轮状病毒。

Input

第一行有1个正整数n。

Output

将编程计算出的不同的n轮状病毒数输出

Sample Input

Sample Output

Source

16

3

16

3做了N久的八中OJ才做第二题晕。。。
这道题首先我的想法是破环为链,再想办法做。。
对于一个链来说,设Dp[i]为长度为i的链和一个“中心”的生成树数量,可以Dp之。。
然后考虑环,枚举1节点所在的环的长度,设为Len,那么这个环的位置有Len种情况,这个环与中心连接也有Len种情况,那么这个节点对答案的贡献就是Len^2*Dp[n-Len]。。
写个高精度+一下久OK了。。。

[Baltic2005]Cards

[Baltic2005]Cards

Time Limit:5000MS Memory Limit:165536K
Total Submit:6 Accepted:6
Case Time Limit:1000MS

Description

Adam在抽屉时发现了一些卡片,他在卡片的正反面随机写了一些数字,然后按其随机排放.
并进行形如下图的计算,问所能得到的最小值为多少.注意Adam可以把卡片翻转过来.

第一行输入数字N,N在[2,100000]且为偶数.
下面N行每行两个数字Ai,Bi,表示Adam写在卡片上的数字.其值在[-2000,2000]

Input

input data1
6
-8 12
0 5
7 -3
10 -7
-2 7

input data2
10
70 70
62 73
81 65
59 77
99 40
35 88
80 57
76 67
85 57
53 96

Output

output data1
-34

output data 2
-155

Sample Input

Sample Output

Hint

Source
水题。很显然如果一个数前面是-号,则要用Max(a,b),否则就是Min(a,b)
神奇的变换来了(*^__^*) 嘻嘻……。。
-2Max(a,b)=-(a+b)-|a-b|,2Min(a,b)=a+b-|a-b|…
所以|a-b|是都有的,故只要按a+b排序就OK了。。。|

COCI 2010-OPEN

最近状态超烂晕死。。比赛的时候一点力气也没有囧。。
第一题挺水的,只要分别按x轴和y轴排序就可以在LogN内回答问题了。。估计也有离线的算法。。我写好之后还不相信那么水就写了个对拍的。。。
第二题就很恶心了。。完全没有思路,只好写个平衡树来骗分,后悔啊,4组数据因为我用Treap只过了2组,如果是Splay的话第二组数据也可以过就是75分了。。不过感觉Splay可能会TLE囧。。。
第三题没什么思路,想了半天感觉只能暴力DP只能拿50分,头晕死了不想写了。。
第四题没看就去睡觉了,太困了囧。。。
PS。特意核对了一下囧

[Sdoi2010]大陆争霸

栗栗的书架那道破题快把我搞疯了冏。。先做到简单的缓缓囧。。。

[Sdoi2010]大陆争霸

Time Limit:10000MS  Memory Limit:65536K
Total Submit:72 Accepted:29
Case Time Limit:1000MS

Description

在一个遥远的世界里有两个国家:位于大陆西端的杰森国和位于大陆东端的
克里斯国。两个国家的人民分别信仰两个对立的神:杰森国信仰象征黑暗和毁灭
的神曾·布拉泽,而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。
幻想历 8012年 1月,杰森国正式宣布曾·布拉泽是他们唯一信仰的神,同
时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。
幻想历 8012年 3月2日,位于杰森国东部小镇神谕镇的克里斯国教徒发动
起义。
幻想历 8012年 3月7日,神谕镇的起义被杰森国大军以残酷手段镇压。
幻想历 8012年 3月8日,克里斯国对杰森国宣战。由数十万大军组成的克
里斯军团开至两国边境,与杰森军团对峙。
幻想历 8012年 4月,克里斯军团攻破杰森军团防线进入神谕镇,该镇幸存
的克里斯国教徒得到解放。
战争随后进入胶着状态,旷日持久。战况惨烈,一时间枪林弹雨,硝烟弥漫,
民不聊生。
幻想历 8012年 5月12日深夜,斯普林·布拉泽降下神谕:“Trust me, earn
eternal life.”克里斯军团士气大增。作为克里斯军团的主帅,你决定利用这一机
会发动奇袭,一举击败杰森国。具体地说,杰森国有 N 个城市,由 M条单向道
路连接。神谕镇是城市 1而杰森国的首都是城市 N。你只需摧毁位于杰森国首都
的曾·布拉泽大神殿,杰森国的信仰,军队还有一切就都会土崩瓦解,灰飞烟灭。
为了尽量减小己方的消耗,你决定使用自爆机器人完成这一任务。唯一的困
难是,杰森国的一部分城市有结界保护,不破坏掉结界就无法进入城市。而每个
城市的结界都是由分布在其他城市中的一些结界发生器维持的,如果想进入某个
城市,你就必须破坏掉维持这个城市结界的所有结界发生器。
现在你有无限多的自爆机器人,一旦进入了某个城市,自爆机器人可以瞬间
引爆,破坏一个目标(结界发生器,或是杰森国大神殿),当然机器人本身也会
一起被破坏。你需要知道:摧毁杰森国所需的最短时间。

Input

第一行两个正整数 N, M。
接下来 M行,每行三个正整数 ui, vi, wi,表示有一条从城市ui到城市 vi的单
向道路,自爆机器人通过这条道路需要 wi的时间。
之后 N 行,每行描述一个城市。首先是一个正整数 li,维持这个城市结界所
使用的结界发生器数目。之后li个1~N 之间的城市编号,表示每个结界发生器的
位置。如果 Li = 0,则说明该城市没有结界保护,保证L1 = 0 。

Output

仅包含一个正整数 ,击败杰森国所需的最短时间。

Sample Input

6 6
1 2 1
1 4 3
2 3 1
2 5 2
4 6 2
5 3 2
0
0
0
1 3
0
2 3 5

Sample Output

5

Hint

对于 20%的数据,满足 N≤15,M≤50;
对于 50%的数据,满足 N≤500,M≤6,000;
对于 100%的数据,满足 N≤3,000,M≤70,000,1≤wi≤108

输入数据保证一定有解,且不会存在维持某个城市结界的结界发生器在这个
城市内部。
连接两个城市的道路可能不止一条, 也可能存在一个城市自己到自己的道路。

Source

第一轮Day1
设第i个城市的最早到达时间是Dpi..那么要满足什么条件呢,Dpi>=Max(Dpt | i受到t保护),
Dpi>=Min(Dpt + t->i | t可以到达i)。。。
然后直接用类似Bellman-Ford的算法迭代就OK了。。。
水题不发代码了。。

[SDOI2009]HH的项链

[SDOI2009]HH的项链

Time Limit:4000MS  Memory Limit:65536K
Total Submit:4 Accepted:2
Case Time Limit:1000MS

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步
完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此,
他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同
的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解
决这个问题。

Input

第一行:一个整数N,表示项链的长度。
第二行:N个整数,表示依次表示项链中贝壳的编号(编号为0到1000000之间的整数)。
第三行:一个整数M,表示HH询问的个数。
接下来M行:每行两个整数,L和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

Output

M行,每行一个整数,依次表示询问对应的答案。

Sample Input

6
1 2 3 4 3 5
3
1 2
3 5
2 6

Sample Output

2
2
4

Hint

对于20%的数据,N ≤ 100,M ≤ 1000;
对于40%的数据,N ≤ 3000,M ≤ 200000;
对于100%的数据,N ≤ 50000,M ≤ 200000。

Source

Day2
首先肯定在线算法是搞不出来的冏,所以离线处理。对每个位置维护到当前考虑到点有多少不同点个。然后每次考虑第i个数时,设Ai上一次出现在第p个。。那么p+1->i的答案全部+1,可以很方便地用树状数组维护。。PS。。把树状数组写成类的形式感觉真爽啊。。
Code:

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>2,maxn=50000+2,maxm=200000,maxd=1000000+1;
using namespace std;
typedef pair<int,int> ii;
int Ans[maxm],A[maxn],P[maxd],n,m;
vector<ii> E[maxn];
struct TArray
{
int A[maxn],n;
void Add(int p,int d)
{
for(;p<=n;p+=(p&-p))A[p]+=d;
}
void Add(int l,int r,int d)
{
Add(l,d);Add(r+1,-d);
}
void Set(int _n){n=_n;For(i,0,n)A[i]=0;}
int operator[](int i)
{
int ret=0;if(!i)return inf;
for(;i;i-=(i&-i))ret+=A[i];
return ret;
}
}T;
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);For(i,1,n)scanf("%d",A+i),P[A[i]]=0;
scanf("%d",&m);int l,r;rep(i,m)scanf("%d%d",&l,&r),E[r].pb(ii(l,i));
T.Set(n);
For(i,1,n)
{
int t=A[i],p=P[t]+1;P[t]=i;
T.Add(p,i,1);
rep(j,E[i].size())Ans[E[i][j].second]=T[E[i][j].first];
}
rep(i,m)printf("%dn",Ans[i]);
}

[Baltic2008]Gloves

[Baltic2008]Gloves

Time Limit:10000MS Memory Limit:165536K
Total Submit:43 Accepted:16
Case Time Limit:1000MS

Description

手套被放在了两个抽屉里, 所有的左手套放在左边的抽屉里, 所有的右手套放在右边的抽屉里.
手套一共有N种颜色, 已知两个抽屉每种颜色的手套各有多少只, 如果随便在左边拿一只, 右边拿一只
很可能会造成拿到一只红色的左手套和一只蓝色右手套… 现想知道应该从左边的抽屉取出多少只左手套(设为x)
右边的抽屉取出多少只右手套(设为y), 满足至少可以找到一对匹配的手套(即颜色相同), 并且x + y最小
如果有多个(x, y)满足x + y最小, 你希望满足x尽可能的小
不妨设 每个抽屉里每只手套被取出的概率是等价的.
输入文件
输入文件第一行中有一个正整数N,表示颜色的种数.
第二行有N个非负整数, 表示左抽屉中每种颜色的左手套的个数.
第三行有N个非负整数, 表示右抽屉中每种颜色的右手套的个数.
输出文件
你需要输出满足题目条件的(x, y).

Input

输入文件第一行中有一个正整数N,表示颜色的种数.
第二行有N个非负整数, 表示左抽屉中每种颜色的左手套的个数.
第三行有N个非负整数, 表示右抽屉中每种颜色的右手套的个数.

Output

输出满足题目条件的(x, y).

Sample Input

Sample Output

Source
饿。。我的算法超级慢,运行了接近6000MS囧。。。
这道题还是有点意思的,一开始我没什么想法,然后注意将这个N个颜色划分成2部分,一种左手套设和为L,一种右手套,设和为R,那么对于任何x<=L&&y<=R的都将不行。。于是枚举所有的划分(1<<n)。。算出每种约束,把所有约束看成点,然后去掉被包含的点,然后按X排序,那么答案只可能出现在两个相邻的点组成的矩形的左下角的右上一格。。很好证明就不多说了。。
Code:

#include<iostream>#include<algorithm>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=20;typedef long long ll;const ll inf=1LL<<60;int A[maxn],B[maxn],n,m=0;ll L=0,R=0;struct Point{ ll x,y; Point(){} Point(ll _x,ll _y):x(_x),y(_y){} bool operator<(const Point&o)const { if(x!=o.x)return x<o.x; return y<o.y; }}P[1<<maxn];void Dfs(int p,ll l,ll r){ if(p==n){P[m++]=Point(l,r);return;} Dfs(p+1,l+A[p],r);Dfs(p+1,l,r+B[p]);}int main(){ //freopen("in","r",stdin); cin>>n;rep(i,n)cin>>A[i],L+=A[i];rep(i,n)cin>>B[i],R+=B[i]; Dfs(0,0,0);sort(P,P+m);int p=0;ll l=inf,r=inf; for(int i=0;i<m;i++) { while(p&&P[p-1].y<=P[i].y)p–; P[p++]=P[i]; } m=p; for(int i=0;i<m-1;i++) { ll a=P[i].x+1,b=P[i+1].y+1; if(!(a<=L&&b<=R))continue; if(a+b>l+r)continue; if(a+b<l+r)l=a,r=b; else if(a<l)l=a,r=b; } cout<<l<<" "<<r<<endl;}2 8100%的测试数据, N <= 20, 0 <= ai, bi <= 108.40 7 1 61 5 0 6

[JSOI2007]字符加密Cipher

[JSOI2007]字符加密Cipher

Time Limit:10000MS Memory Limit:165536K
Total Submit:76 Accepted:34
Case Time Limit:1000MS

Description

喜欢钻研问题的JS 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。例如下图,可以读作:

JSOI07
SOI07J
OI07JS
I07JSO
07JSOI
7JSOI0
把它们按照字符串的大小排序:
07JSOI
7JSOI0
I07JSO
JSOI07
OI07JS
SOI07J
读出最后一列字符:I0O7SJ,就是加密后的字符串(其实这个加密手段实在很容易破解,鉴于这是突然想出来的,那就^^)。
但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?

Input

输入文件包含一行,欲加密的字符串。注意字符串的内容不一定是字母、数字,也可以是符号等。

Output

输出一行,为加密后的字符串。

Sample Input

Sample Output

Source
很显然,暴力上后缀数组。。。哎。原来觉得后缀数组很难,现在随便写了,看来事在人为啊囧。。
Code:

#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=100000*2+1;int n,m,sa[maxn],ta[maxn],tb[maxn],*x=ta,*y=tb;char C[maxn];bool cmp(int i,int j,int l){ return y[i]==y[j]&&y[i+l]==y[j+l];}void Sort(){ static int w[maxn]; rep(i,m)w[i]=0;rep(i,n)w[x[y[i]]]++; rep(i,m-1)w[i+1]+=w[i]; for(int i=n-1;i>=0;i–)sa[–w[x[y[i]]]]=y[i];}void Da(){ int i,j,p; rep(i,n)x[i]=C[i],y[i]=i;Sort(); for(p=1,j=1;p<n;m=p,j*=2) { for(p=0,i=n-j;i<n;i++)y[p++]=i; rep(i,n)if(sa[i]>=j)y[p++]=sa[i]-j;Sort(); for(swap(x,y),i=1,p=1,x[sa[0]]=0;i<n;i++) x[sa[i]]=cmp(sa[i-1],sa[i],j)?p-1:p++; }}int main(){ //freopen("in","r",stdin); gets(C);n=strlen(C); rep(i,n)C[n+i]=C[i];n<<=1;C[n++]=0;m=256; Da();int s=n/2; rep(i,n)if(sa[i]<s)printf("%c",C[s+sa[i]-1]); printf("n");}I0O7SJ数据规模对于40%的数据字符串的长度不超过10000。对于100%的数据字符串的长度不超过100000。JSOI07

[Sdoi2010]地精部落

[Sdoi2010]地精部落

Time Limit:10000MS  Memory Limit:65536K
Total Submit:5 Accepted:5
Case Time Limit:1000MS

Description

传说很久以前,大地上居住着一种神秘的生物:地精。
地精喜欢住在连绵不绝的山脉中。具体地说,一座长度为 N 的山脉 H可分
为从左到右的 N 段,每段有一个独一无二的高度 Hi,其中Hi是1到N 之间的正
整数。
如果一段山脉比所有与它相邻的山脉都高,则这段山脉是一个山峰。位于边
缘的山脉只有一段相邻的山脉,其他都有两段(即左边和右边)。
类似地,如果一段山脉比所有它相邻的山脉都低,则这段山脉是一个山谷。
地精们有一个共同的爱好——饮酒,酒馆可以设立在山谷之中。地精的酒馆
不论白天黑夜总是人声鼎沸,地精美酒的香味可以飘到方圆数里的地方。
地精还是一种非常警觉的生物,他们在每座山峰上都可以设立瞭望台,并轮
流担当瞭望工作,以确保在第一时间得知外敌的入侵。
地精们希望这N 段山脉每段都可以修建瞭望台或酒馆的其中之一,只有满足
这个条件的整座山脉才可能有地精居住。
现在你希望知道,长度为N 的可能有地精居住的山脉有多少种。两座山脉A
和B不同当且仅当存在一个 i,使得 Ai≠Bi。由于这个数目可能很大,你只对它
除以P的余数感兴趣。

Input

仅含一行,两个正整数 N, P。

Output

仅含一行,一个非负整数,表示你所求的答案对P取余
之后的结果。

Sample Input

4 7

Sample Output

3

Hint


对于 20%的数据,满足 N≤10;
对于 40%的数据,满足 N≤18;
对于 70%的数据,满足 N≤550;
对于 100%的数据,满足 3≤N≤4200,P≤109

Source

第一轮Day2
操。。BS这帮出题的操SGU原题。。。以前的题解。。

hi.baidu.com/wjbzbmr/blog/item/cc691324d15ed21c8b82a115.html

Zju2112 Dynamic Rankings

Zju2112 Dynamic Rankings

Time Limit:10000MS  Memory Limit:165536K
Total Submit:18 Accepted:7
Case Time Limit:1000MS

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在 a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对 改变后的a继续回答上面的问题。
你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。

第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。
第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。
接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。
Q i j k 或者 C i t
Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。

Input

对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。

Output

Sample Input

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6

Hint

20%的数据中,m,n≤100;
40%的数据中,m,n≤1000;
100%的数据中,m,n≤10000。

Source

各位神牛至少3KB的代码量让我很冏。。一般来说是要树套树的把,但我感觉那样很难写,索性写个块状数组算了。。结果发现速度非常快冏。。。
对每个块保存排序的结果,同时保存整体所有的数,那么查询一个数在一个区间中比它小的数数量是
O(N^0.5LogN)的。。再加上二分找这个数,就是N^0.5*LogN^2了。。
还有修改的话直接修改一排序的结果(插入排序)和整体这个数,是O(N^0.5)的。。但我感觉查询都那么慢了修改也无所谓了,就暴力sort了冏。。。由于这里不能搞出当前所有数的排列,所以二分只能按照Log(10^9)=30来搞,实际上如果先离线一下读入所有数就可以直接在所有数中二分,那么就是Log(20000)=15..快一倍。。不过没必要。。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,l,r) for(int i=l;i<=r;i++)
#define pb push_back
const int inf=~0U>>1,maxn=10000,size=100;
int T[size][size],N[size]={},A[maxn],n,m,t,d=1<<6;
using namespace std;
void init()
{
scanf("%d%d",&n,&m);rep(i,n)scanf("%d",A+i),T[i/size][N[i/size]++]=A[i];
t=1+(n-1)/size;rep(i,t)sort(T[i],T[i]+N[i]);
}
int get(int*A,int s,int x)
{
int i,l;
for(i=s,l=d;l;l>>=1)
if(i-l>=0&&A[i-l]>=x)i-=l;
return i;
}
int Count(int l,int r,int x)
{
int a=l/size,b=r/size,s=0;;
if(a==b){For(i,l,r)s+=A[i]<x;return s;}
For(i,l,(a+1)*size-1)s+=A[i]<x;
For(i,b*size,r)s+=A[i]<x;a++;b–;
For(i,a,b)s+=get(T[i],N[i],x);
return s;
}
int kth(int l,int r,int k)
{
#define C(x) (Count(l,r,x))
int i,d;
for(i=0,d=1<<30;d;d>>=1)
if(C(i+d)<k)i+=d;
return i;
}
void Change(int p,int x)
{
int a=p/size;int t=A[p];A[p]=x;
t=lower_bound(T[a],T[a]+N[a],t)-T[a];
T[a][t]=x;sort(T[a],T[a]+N[a]);
}
int main()
{
//freopen("in","r",stdin);
init();char c;int i,j,k;
while(m–)
{
scanf("n%c",&c);
if(c==’C’)scanf("%d%d",&i,&j),Change(i-1,j);
else scanf("%d%d%d",&i,&j,&k),printf("%dn",kth(i-1,j-1,k));
}
}

[Sdoi2009]Elaxia的路线

[Sdoi2009]Elaxia的路线

Time Limit:4000MS  Memory Limit:65536K
Total Submit:3 Accepted:2
Case Time Limit:1000MS

Description

最近,Elaxia和w**的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们
必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间,他们
希望在节约时间的前提下,一起走的时间尽可能的长。
现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图:地图上有N个路
口,M条路,经过每条路都需要一定的时间。
具体地说,就是要求无向图中,两对点间最短路的最长公共路径。

Input

第一行:两个整数N和M(含义如题目描述)。
第二行:四个整数x1、y1、x2、y2(1 ≤ x1 ≤ N,1 ≤ y1 ≤ N,1 ≤ x2 ≤ N,1 ≤
≤ N),分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号(两对点分别
x1,y1和x2,y2)。
接下来M行:每行三个整数,u、v、l(1 ≤ u ≤ N,1 ≤ v ≤ N,1 ≤ l ≤ 10000),表
u和v之间有一条路,经过这条路所需要的时间为l。
出出出格格格式式式:::
一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)。

Output

一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)

Sample Input

9 10
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1

Sample Output

3

Hint

对于30%的数据,N ≤ 100;
对于60%的数据,N ≤ 1000;
对于100%的数据,N ≤ 1500,输入数据保证没有重边和自环。

Source

Day2
额。。看上去很吓人,实际上还是蛮水的。。
首先可以注意到公共的路径必然是一段。。然后找出所有可以同时出现在两个最短路的边,用Dp求出最长的链就OK了。。。
Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=1500;
using namespace std;
int n,m,S[2],T[2];
struct Edge
{
int t,c;Edge*next;
Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}
}*E[maxn]={};
void AddEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,c,E[t]);
}
int DistS[2][maxn],DistT[2][maxn];
struct Queue
{
int Q[maxn],h,t;bool inQ[maxn];
Queue(){h=t=0;memset(inQ,0,sizeof(inQ));}
void inc(int&i){if(++i==maxn)i=0;}
void put(int x)
{
if(inQ[x])return;inQ[x]=true;
Q[t]=x;inc(t);
}
int get()
{
int tmp=Q[h];inc(h);inQ[tmp]=false;
return tmp;
}
bool empty(){return h==t;}
};
void Spfa(int vs,int Dist[maxn])
{
static Queue Q;
rep(i,n)Dist[i]=inf;Dist[vs]=0;Q.put(vs);
while(!Q.empty())
{
int t=Q.get(),c=Dist[t];
for(Edge*e=E[t];e;e=e->next)
if(c+e->c<Dist[e->t])
Dist[e->t]=c+e->c,Q.put(e->t);
}
}
int D[2];
bool inPath(int v)
{
rep(i,2)if(DistS[i][v]+DistT[i][v]!=D[i])return false;
return true;
}
bool inPath(int s,Edge*e)
{
rep(i,2)
{
int Dist=min(DistS[i][s]+DistT[i][e->t],DistS[i][e->t]+DistT[i][s])+e->c;
if(Dist!=D[i])return false;
}
return true;
}
bool In[maxn]={};
int A[maxn],v=0,Dp[maxn]={};
bool cmp(int i,int j)
{
return DistS[0][i]<DistS[0][j];
}
int main()
{
//freopen("in","r",stdin);
scanf("%d%d%d%d%d%d",&n,&m,S+0,T+0,S+1,T+1);int s,t,c;
rep(i,2)S[i]–,T[i]–;
while(m–)scanf("%d%d%d",&s,&t,&c),–s,–t,AddEdge(s,t,c);
rep(i,2)Spfa(S[i],DistS[i]),Spfa(T[i],DistT[i]);
rep(i,2)D[i]=DistS[i][T[i]];
rep(i,n)In[i]=inPath(i),In[i]?A[v++]=i:0;
sort(A,A+v,cmp);
int ans=0;
rep(i,v)
{
int t=A[i];ans>?=Dp[t];
for(Edge*e=E[t];e;e=e->next)if(In[e->t]&&inPath(t,e))
Dp[e->t]>?=Dp[t]+e->c;
}
cout<<ans<<endl;
}

Page 30 of 56« First...1020...2829303132...4050...Last »