记录编号	594346	评测结果	AMATMAAMWTTT
题目名称	[POJ 3463] 观光	最终得分	33
用户昵称	郑霁桓	是否通过	未通过
代码语言	C++	运行时间	14.092 s
提交时间	2024-09-28 16:36:06	内存使用	33.72 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,z,s[1005],tp,sy[1005];
long long T,d[1005],pp,st,ed,t,dy[1005];
queue<pair<long long,long long> >q;
vector<pair<long long,long long> >v[1005];
inline long long read(){
    long long xx=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=(xx<<1)+(xx<<3)+(ch^48);
        ch=getchar();
    }
    return xx;
}
inline void write(long long x){
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return;
}
int main(){
    freopen("sightseeing.in","r",stdin);
    freopen("sightseeing.out","w",stdout);
    T=read();
    while(T--){
        n=read();
        m=read();
        for(int i=1;i<=n;i++){
            v[i].clear();
            s[i]=0;
        }
        while(!q.empty()){
            q.pop();
        }
    	for(int i=1;i<=m;i++){
    		x=read();
    		y=read();
    		z=read();
    		v[x].push_back({y,z});
    	}
    	st=read();
        ed=read();
    	q.push({st,0});
    	for(int i=1;i<=n;i++){
    		d[i]=100000000000;
    	}
    	while(!q.empty()){
    		tp=q.front().first;
    		pp=q.front().second;
    		q.pop();
    		if(pp<d[tp]){
    			s[tp]=1;
    			d[tp]=pp;
    		}else if(pp==d[tp]){
    			s[tp]++;
    		}else{
    			continue;
    		}
    		for(int i=0;i<v[tp].size();i++){
    			if(d[tp]+v[tp][i].second<=d[v[tp][i].first]){
    				q.push({v[tp][i].first,d[tp]+v[tp][i].second});
    			}
    		}
    	}
    	while(!q.empty()){
            q.pop();
        }
    	q.push({st,0});
    	for(int i=1;i<=n;i++){
    		dy[i]=100000000000;
    	}
    	while(!q.empty()){
    		tp=q.front().first;
    		pp=q.front().second;
    		q.pop();
    		if(pp>d[tp]&&pp<dy[tp]){
    			sy[tp]=1;
    			dy[tp]=pp;
    		}else if(pp==dy[tp]){
    			sy[tp]++;
    		}else if(pp>dy[tp]||(tp!=st&&pp==d[tp])){
    		    continue;
            }
    		for(int i=0;i<v[tp].size();i++){
    			if(dy[tp]+v[tp][i].second<=dy[v[tp][i].first]){
    				q.push({v[tp][i].first,dy[tp]+v[tp][i].second});
    			}
    			if(d[tp]+v[tp][i].second<=dy[v[tp][i].first]){
    				q.push({v[tp][i].first,d[tp]+v[tp][i].second});
    			}
    		}
    	}
    	if(dy[ed]==d[ed]+1){
    	    s[ed]+=sy[ed];
        }
        write(s[ed]);
        puts("");
    }
	return 0;
}