Submission #2385291

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<ll,ll> P;
const ll MOD=10000;
const ll INF=1000000010;
const ll LINF=1000000000000000010;
const int MAX=100001;
int dx[8]={0,1,0,-1,1,-1,1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
vector<P> G[3010];
int main(){
    int n,m,r,t;
    cin>>n>>m>>r>>t;
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        a--;b--;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        vector<int> v1(n,INF);
        vector<int> v2(n,INF);
        priority_queue<P,vector<P>,greater<P> > q;
        q.push(P(0,i));
        v1[i]=0;
        while(!q.empty()){
            P p=q.top();q.pop();
            for(auto e:G[p.second]){
                if(e.second+p.first>=v1[e.first])continue;
                v1[e.first]=e.second+p.first;
                q.push(P(v1[e.first],e.first));
            }
        }
        v2=v1;
        for(int j=0;j<n;j++){
            v1[j]*=t;
            v2[j]*=r;
        }
        if(t>r){
            ans-=n-1;
        }
        sort(v2.begin(),v2.end());
        for(int j=0;j<n;j++){
            if(i==j)continue;
            ll p=upper_bound(v2.begin(),v2.end(),v1[j]-1)-v2.begin();
            ans+=p-1;
        }
    }
    cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result