P1094 -- 路径
时间限制：1000MS
内存限制：65536KB
Description
给定一张带权有向图，现在你可以从任意点出发，但是要求要找到一条路径（可以走重边），并且这条路径的长度小于-19910917917，问这种路径是否存在？
Input Format
输入数据包括一个N和一个M，表示点数和边数。接下来M行，每行有3个整数A、B、C，表示从A向B连出一条权值为C的边。
Output Format
输出包括一个字符“Y”或“N”，“Y”表示存在，“N”表示不存在。
Sample Input
3 41 2 12 3 -13 1 13 1 -1
Sample Output
Y
Hint
对于40%的数据，边数不超过10。 对于100%的数据，点数不超过10000，边数不超过10000，权C绝对值不超过300000。
【题解】
TAT又WA了n多次
我以为STL的队列被卡时间了QAQ后来发现并没有
是我自己搞错了
首先，outqueue的次数设定为10即可。
然后，low一定要开long long！因为10000*-300000要。。。了
TAT我就这样WA了无数次
好歹最后0.028s排到rank2
1 #include2 using namespace std; 3 const int MAX=10010; 4 struct node { 5 int to,w,next; 6 }edge[MAX]; 7 bool used[MAX]; 8 int outqueue[MAX],head[MAX]; 9 long long low[MAX];10 int n,m;11 char B[1<<15],*S=B,*T=B;12 char getchar2() {13 return S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++;14 }15 int read() {16 int x=0,f=1;17 char ch=getchar2();18 while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar2();}19 while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0'; ch=getchar2();}20 return x*f;21 }22 23 bool spfa() {24 queue q;25 used[1]=1;26 for (int i=1;i<=n;++i) q.push(i);27 while(!q.empty()) {28 int top=q.front();29 q.pop();used[top]=0;30 outqueue[top]++;31 if(outqueue[top]>10) return 0;32 for (int k=head[top];k!=-1;k=edge[k].next)33 if(low[edge[k].to]>low[top]+edge[k].w) {34 low[edge[k].to]=low[top]+edge[k].w;35 if(!used[edge[k].to]) {36 used[edge[k].to]=1;37 q.push(edge[k].to);38 }39 }40 }41 return 1;42 }43 int main() {44 memset(used,0,sizeof(used));45 memset(head,-1,sizeof(head));46 memset(outqueue,0,sizeof(outqueue));47 memset(low,0,sizeof(low));48 n=read();m=read();49 for (int i=1,k=0,from,to,wei; i<=m; ++i) {50 from=read();to=read();wei=read();51 edge[k].to=to;52 edge[k].w=wei;53 edge[k].next=head[from];54 head[from]=k++;55 }56 if(spfa()) printf("N\n");57 else printf("Y\n");58 return 0;59 }