[dij,暴力] 2020牛客国庆集训派对day3- B First Date

题目：https://ac.nowcoder.com/acm/contest/7830/B
n和m都很少，可以1e4次建图+dij暴力算期望
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned long long ull;
  5 //typedef __int128_t LL;
  6 typedef double db;
  7 #define rep(a,b,c) for(ll a=b;a<=c;a++)
  8 #define per(a,b,c) for(ll a=b;a>=c;a--)
  9 #define go(a,b) for(ll a=head[b];a;a=e[a].to)
 10 #define endl '
'
 11 #define V vector
 12 #define pb push_back
 13 #define mp make_pair
 14 #define mem(a,b) memset(a,b,sizeof(a))
 15 const ll amn=1e5+5,mod=1e9+7,inf=0x3f3f3f3f;
 16 ll head[amn],etot;
 17 struct eg{
 18     ll to,v;
 19     db w;
 20     eg(){}
 21     eg(ll to,ll v,db w):to(to),v(v),w(w){}
 22 }e[amn];
 23 void einit(){
 24     etot=0;
 25     mem(head,0);
 26 }
 27 void add(ll u,ll v,db w){
 28     e[++etot]=eg(head[u],v,w);
 29     head[u]=etot;
 30 }
 31 void sovle();
 32 int main(){
 33     ios::sync_with_stdio(0);
 34     ll T=1;
 35     //cin>>T;
 36     while(T--){
 37         sovle();
 38     }
 39 }
 40 ll n,m,k;
 41 ll s,t;
 42 struct Node{
 43     int id; db d;
 44     Node() {}
 45     Node(int id, db d):id(id),d(d){}
 46     bool operator < (const Node &A) const {
 47         return d > A.d;
 48     }
 49 };
 50 ll vis[amn];
 51 db dis[amn];
 52 void dijkstra(int st){
 53     for(int i=1; i<=n; i++){
 54         vis[i] = 0;
 55         dis[i] = inf;
 56     }
 57 
 58     dis[st] = 0;
 59     priority_queue <Node> Q;
 60     while(Q.size())Q.pop();
 61     Q.push(Node(st, 0));
 62     Node nd;
 63 
 64     while(!Q.empty()){
 65         nd = Q.top(); Q.pop();
 66         if(vis[nd.id]) continue;
 67         vis[nd.id] = true;
 68         go(i,nd.id){
 69             int j = e[i].v;
 70             db k = e[i].w;
 71             if(nd.d + k < dis[j] && !vis[j]){
 72                 dis[j] = nd.d + k;
 73                 Q.push(Node(j, dis[j]));
 74             }
 75         }
 76     }
 77 }
 78 ll u[amn],v[amn];
 79 db x[amn],y[amn];
 80 void sovle(){
 81     cin>>n>>m>>s>>t;
 82     rep(i,1,m){
 83         cin>>u[i]>>v[i]>>x[i]>>y[i];
 84     }
 85     db ans=0,bs=1e-4;
 86     for(db a=bs;a<=1;a+=bs){
 87         einit();
 88         rep(i,1,m){
 89             db w=x[i]+a*y[i];
 90             add(u[i],v[i],w);
 91             add(v[i],u[i],w);
 92         }
 93         dijkstra(s);
 94         ans+=dis[t];
 95     }
 96     cout<<ans/(1e4)<<endl;
 97 }
 98 /*
 99 
100 */