* bzoj 3040 최 단 로 (road) 문제 풀이

전재 설명:http://blog.csdn.net/jiangshibiao/article/details/22776055
[원제]
3040: 최 단 로 (road)
Time Limit: 60 Sec  
Memory Limit: 200 MB
Submit: 1036  
Solved: 262
[ Submit][ Status]
Description
N 개의 점, M 개의 변 에 방향 그림 이 있 고 1 에서 N 의 최 단 로 를 구 합 니 다 (존재 보장).1<=N<=1000000，1<=M<=10000000
Input
첫 줄 의 두 정수 N, M 은 포인트 와 변 수 를 나타 낸다.두 번 째 줄 여섯 개의 정수 T, rxa, rxc, rya, ryc, rp.
앞의 T 조 는 다음 과 같은 방식 으로 생 성 됩 니 다. 1. x = y = z = 0 을 초기 화 합 니 다.2. 다음 과정 T 회 반복: x = (x * rxa + rxc)% rp;y=(y*rya+ryc)%rp; a=min(x%n+1,y%n+1); b=max(y%n+1,y%n+1); a 에서 b 까지 길이 가 1e8 - 100 * a 인 방향 변 이 있 습 니 다.
후 M - T 줄 은 읽 기 방식 을 사용한다. 다음 M - T 줄 은 줄 마다 세 개의 정수 x, y, z 로 x 에서 y 까지 길이 가 z 인 방향 을 나타 낸다.
1<=x,y<=N，0
Output
하나의 정 수 는 1 ~ N 의 최 단 로 를 나타 낸다.
Sample Input
3 3 0 1 2 3 5 7 1 2 1 1 3 3 2 3 1
Sample Output
2
HINT
[주석] 효율 적 인 더 미 를 사용 하여 Dijkstra 알고리즘 을 최적화 하 십시오.
Source
WC 2013 영업 사원 교류 - lydranbowcat
[분석] 완전 dijkstra 의 최적화!근 데 이 메모리 가 너무 꽉 끼 네요.한 번 은 비참 한 문제 풀이 경험 이다.
[NUM. 1 - 시스템 더미] (제출 후 lld 로 변경)

#include
#include
#include
#include
#include
//#include
//#include
using namespace std;
typedef long long ll;
typedef pairPair;
const int N=1000005;
const int M=10000005;
ll x,y,z,rxa,rxc,rp,rya,ryc,aa,bb,dis[N],cnt;
struct arr{int next,go,s;}a[M];
int xx,yy,t,i,now,n,m,end[N],go;
bool flag[N];
priority_queue< Pair,vector,greater >q;
void make_up(int u,int v,int w)
{
  a[++cnt].go=v;a[cnt].s=w;a[cnt].next=end[u];end[u]=cnt;
}
int main()
{
  scanf("%d%d",&n,&m);
  scanf("%d%I64d%I64d%I64d%I64d%I64d",&t,&rxa,&rxc,&rya,&ryc,&rp);
  x=y=z=0;
  for (i=1;i<=t;i++)
  {
    x=(x*rxa+rxc)%rp;y=(y*rya+ryc)%rp;
    aa=min(x%n+1,y%n+1);bb=max(y%n+1,y%n+1);
    make_up((int)aa,(int)bb,100000000-100*aa);
  }
  for (i=1;i<=m-t;i++)
  {
    scanf("%d%d%d",&xx,&yy,&z);
    make_up(xx,yy,z);
  }
  memset(dis,60,sizeof(dis));dis[1]=0;
  q.push(pair(dis[1],1));
  while (!q.empty())
  {
    Pair temp=q.top();q.pop();
    now=temp.second;
    flag[now]=true;
    for (i=end[now];i;i=a[i].next)
    {
      go=a[i].go;
      if (dis[go]>dis[now]+ll(a[i].s)&&!flag[go])
      {
        dis[go]=dis[now]+ll(a[i].s);q.push(make_pair(dis[go],go));
      }
    }
  }
  printf("%I64d",dis[n]);
  return 0;
}

하지만 5s 정도 실행 하면 메모리 가 터 집 니 다 ~ ~ RZZ 큰 소 는 반복 적 으로 쌓 여 있 는 상황 이 있어 동적 인 quue 메모리 가 터 졌 기 때 문 이 라 고 말 합 니 다.
[NUM 2 - 수공 더미]

#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pairPair;
const int N=1000005;
const int M=10000005;
ll x,y,rxa,rxc,rp,rya,ryc,aa,bb,dis[N],go,cnt,pre[N],end[N];
Pair d[N*2];char ch;
struct arr{int next,go,s;}a[M];
bool flag[N];
int xx,yy,z,t,i,now,n,m,len;
void make_up(int u,int v,int w)
{
  a[++cnt].go=v;a[cnt].s=w;a[cnt].next=end[u];end[u]=cnt;
}
void swap(Pair &a,Pair &b)
{
  Pair c=a;a=b;b=c;
}
void pop()
{
  pre[d[1].second]=0;pre[d[len].second]=1;d[1]=d[len];len--;
  int now=1;
  while (true)
  {
    ll t1=d[now].first,t2=d[now*2].first,t3=d[now*2+1].first;
    if (t21)
  {
    pre[p]=now/2;pre[d[now/2].second]=now;
    swap(d[now],d[now/2]);now/=2;
  }
}
void push(Pair that)
{
  d[++len]=that;int now=len,p=that.second;pre[p]=len;
  up(now,p);
}
int Read()
{
  while (ch'9') ch=getchar();
  int s=0;
  while (ch>='0'&&ch<='9') s=s*10+ch-48,ch=getchar();
  return s;
}
int main()
{
  scanf("%d%d",&n,&m);
  scanf("%d %lld %lld %lld %lld %lld",&t,&rxa,&rxc,&rya,&ryc,&rp);
  x=y=z=0;
  for (i=1;i<=t;i++)
  {
    x=(x*rxa+rxc)%rp;y=(y*rya+ryc)%rp;
    aa=min((ll)x%n+1,(ll)y%n+1);bb=max(ll(y%n+1),ll(y%n+1));
    make_up((int)aa,(int)bb,(int)100000000-100*aa);
  }
  ch='!';
  for (i=1;i<=m-t;i++)
  {
    xx=Read();yy=Read();z=Read();
    make_up(xx,yy,z);
  }
  memset(dis,60,sizeof(dis));
  memset(pre,0,sizeof(pre));
  dis[1]=0;push(make_pair(dis[1],1));len=1;pre[1]=1;
  while (len)
  {
    Pair temp=d[1];pop();
    now=temp.second;flag[now]=true;
    for (i=end[now];i;i=a[i].next)
    {
      go=a[i].go;
      if (dis[go]>dis[now]+ll(a[i].s)&&!flag[go])
      {
        dis[go]=dis[now]+ll(a[i].s);
        if (pre[go]==0) push(make_pair(dis[go],go));
        else 
        {
          d[pre[go]].first=dis[go];
          up(go,d[pre[go]].second);
        }
      }
      
    }
  }
  printf("%lld",dis[n]);
  return 0;
}

이 곳 의 수 제 더미 의 정확성 은 그다지 보장 되 지 않 습 니 다. 제 가 많이 쓰 지 않 았 기 때 문 입 니 다. 처음에 T 를 계속 했 을 때 저 는 읽 기 최 적 화 를 추 가 했 습 니 다. 그리고 매 핑 표를 열 어 이미 쌓 여 있 는 dis 값 을 업 데 이 트 했 습 니 다. 마지막 으로 5s 때 WA 가 되 었 습 니 다!!
[결과] SYC 대신 A 가 지나 갔다 고 들 었 습 니 다. 그의 코드 를 자세히 보 니 나의 NUM. 1 과 비슷 합 니 다 ~ 자세히 보 니 그 가 알파벳 하 나 를 잘못 걸 었 군요. 모두 T 개의 변 이 생 성 되 었 지만 그 는 N 개의 변 만 생 성 했 습 니 다! 그래서 나 는 t 도 n 으로 바 꾸 고 지 나 갔 습 니 다 ~ ~ ~ ~ ~
[정 해] 물론 카드 데이터 의 행동 이 죠!! 피 보 나치 더미 나 시스템 으로 짝 을 지어 야 한다 고 합 니 다. 그럼 나중에 연구 해 보 겠 습 니 다 ~ ~