161114-练习-DAY1-AHSDFZ T3

很久很久以前有一个国家，这个国家有 N 个城市，城市由 1，2，3，…，,N 标号，城市间有 M 条双向道路，每条道路都有两个属性 g 和 s ，两个城市间可能有多条道路，并且可能存在将某一城市与其自身连接起来的道路。后来由于战争的原因，国王不得不下令减小花费从而关闭一些道路，但是必须要保证任意两个城市相互可达。

道路花费的计算公式为 wG*max{所有剩下道路的属性g}+wS*max{所有剩下道路的属性s}，其中 wG 和 wS 是给定的值。国王想要在满足连通性的前提下使这个花费最小，现在需要你计算出这个花费。

第一行包含两个正整数 N 和 M 。
第二行包含两个正整数 wG 和 wS 。
后面的 M 行每行描述一条道路，包含四个正整数 u，v，g，s，分别表示道路连接的两个城市以及道路的两个属性。

输出一个整数，表示最小花费。若无论如何不能满足连通性，输出 -1 。

输入　 [复制]

3 3 
2 1 
1 2 10 15 
1 2 4 20 
1 3 5 1

输出

30

【数据规模与约定】
对于 10% 的数据，N≤10；M≤20；
对于 30% 的数据，N≤100；M≤1000；
对于 50% 的数据，N≤200；M≤5000；
对于 100% 的数据，N≤400；M≤50000；wG,wS,g,s≤1000000000

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=50001;
struct node
{
  int go;
  int to;
  int g;
  int s;
}ed[N];
int n,m,fa[401];
int sta[401],tot,num;
long long wG,wS;
long long ans=2e18+5;
inline int Ri()
{
  char c;
  int i=1,f=0;
  for(c=getchar();(c>‘9‘||c<‘0‘)&&c!=‘-‘;c=getchar());
  if(c==‘-‘)
  { 
    i=-1;
    c=getchar();
  }
  for(;c<=‘9‘&&c>=‘0‘;c=getchar())
    f=(f+(f<<2)<<1)+(c^‘0‘);
  return f*i;
}
inline long long Rl()
{
  char c;
  long long i=1,f=0;
  for(c=getchar();(c>‘9‘||c<‘0‘)&&c!=‘-‘;c=getchar());
  if(c==‘-‘)
  { 
    i=-1;
    c=getchar();
  }
  for(;c<=‘9‘&&c>=‘0‘;c=getchar())
    f=(f+(f<<2)<<1)+(c^‘0‘);
  return f*i;
}
inline int getfa(int x)
{
  if(fa[x]==x)  return x;
  else return getfa(fa[x]);
}
inline void comb(int x,int y)
{
  int Fx=getfa(x);
  int Fy=getfa(y);
  if(Fx!=Fy)
    fa[Fx]=Fy;
}
bool comp(node a,node b)
{
  if(a.g==b.g) return a.s<b.s;
  return a.g<b.g;
}
int main()
{
  //freopen("a.in","r",stdin);
  n=Ri();
  m=Ri();
  wG=Rl();
  wS=Rl();
  for(int i=1;i<=m;i++)
  {
    ed[i].go=Ri();
    ed[i].to=Ri();
    ed[i].g=Ri();
    ed[i].s=Ri();
  }
  sort(ed+1,ed+m+1,comp);
  tot=0;
  int j;
  for(int i=1;i<=m;i++)
  {
    for(j=1;j<=n;j++)
      fa[j]=j;
    for(j=tot;j>=1;j--)
    {
      if(ed[sta[j]].s>ed[i].s)
        sta[j+1]=sta[j];
      else 
        break;
    }
    tot++,sta[j+1]=i;
    num=0;
    for(j=1;j<=tot;j++)
    {
      int Fg=getfa(ed[sta[j]].go); 
      int Ft=getfa(ed[sta[j]].to);
      if(Fg!=Ft)
      {
        fa[Fg]=Ft;
        sta[++num]=sta[j];
      }
    }
    if(num==n-1)
      ans=min(ans,ed[sta[num]].s*wS+ed[i].g*wG);
    tot=num;
  }
  if(ans==2e18+5)  cout<<"-1"<<endl;
  else cout<<ans<<endl;
  return 0;
}