結果

提出番号	1967
提出者	T.M
言語	C++
提出日時	2018-08-04 14:45:59
問題名	(73)観光計画
結果	AC
点数	100%

---

テストケース

ソースコード

#include<stdio.h>
long long R=1,C=1,H[2000010],N[2000010];
long long MAX(long long a,long long b){return a<b?b:a;}
//評価関数（いまはMIN）
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//挿入関数
void hin(long long a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//取り出す関数
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
long long CO[100010];
long long i,id[600010],ta[600010],nt[600010],f[600010]={0};
void dijk(int v,int e,int *fr,int *to,int *co,int mi){
  for(i=0;i<v;i++)ta[i]=-1;
  for(i=0;i<v;i++)CO[i]=1e17;
  for(i=CO[mi]=0;i<e;i++){
    nt[i]=ta[fr[i]];
    ta[fr[i]]=i;
  }
  while(f[mi]-1){
    f[mi]=1;
    for(i=ta[mi];i+1;i=nt[i]){
      if(CO[to[i]]>CO[mi]+co[i])hin(CO[id[R]=to[i]]=CO[mi]+co[i]);
    }
    while(f[mi]&&C-1)mi=id[hout()];
  }
}
int main(){
  int n,m,k,i,a[600010],b[600010],c[600010],e[100010],f[100010],max=0;
  scanf("%d %d %d",&n,&m,&k);
  for(i=0;i<m;i++)scanf("%d %d %d",&a[i],&b[i],&c[i]);
  for(i=0;i<k;i++){
    scanf("%d %d",&e[i],&f[i]);
    max=MAX(max,f[i]);
  }
  for(i=0;i<k;i++){
    a[i+m]=0;
    b[i+m]=e[i];
    c[i+m]=max-f[i];
  }
  for(i=0;i<m+k;i++){
    a[i+m+k]=b[i];
    b[i+m+k]=a[i];
    c[i+m+k]=c[i];
  }
  dijk(n+1,m+k+m+k,a,b,c,0);
  for(i=k=0;i<n;i++){
    if(CO[i+1]<=max)k++;
  }
  printf("%d\n",k);
  return 0;
}