有趣的赛车比赛

这个,我还在编译错误,莫名其妙就AC了,我只有一个感觉,懵逼。这个就是正统的dijkstra算法

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
const int INF=999999999;
using namespace std;
typedef pair<int ,int > P;
int n,m,s,t;
struct edge
{
  int to;
  int open;
  int close;
  int cost;
};
vector<edge>G[330];
int d[330];
void init()
{
  for(int i=0;i<330;i++)G[i].clear();
}
void dijkstra()
{
  priority_queue<P,vector<P>,greater<P> >que;
  for(int i=0;i<320;i++)d[i]=INF;
  d[s]=0;
  que.push(P(0,s));
  while(!que.empty())
  {
    P p=que.top();
        que.pop();
    int v=p.second;
    if(d[v]<p.first)continue;
    for(int i=0;i<G[v].size();i++)
    {
      edge e=G[v][i];
      int tmp=p.first,mod=e.open+e.close;
      int re=tmp%mod;
      if(re<e.open&&e.open-re>=e.cost)
      {
        if(d[e.to]>tmp+e.cost)
        {
            d[e.to]=tmp+e.cost;
            que.push(P(d[e.to],e.to));
        }
      }
      else if(e.open>=e.cost)
      {
        if(d[e.to]>tmp+e.cost+mod-re)
        {
           d[e.to]=tmp+e.cost+mod-re;
           que.push(P(d[e.to],e.to));
        }
      }
    }
  }
}

int main()
{
  int test=1;
  while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)
  {
    for(int i=0;i<m;i++)
    {
      int u,v,a,b,t1;
      scanf("%d%d%d%d%d",&u,&v,&a,&b,&t1);


      edge e;
      e.to=v;
      e.open=a;
      e.close=b;
      e.cost=t1;
      G[u].push_back(e);
    }


    dijkstra();
      init();
    printf("Case %d: %d
",test++,d[t]);

  }
  return 0;
}

  

原文地址:https://www.cnblogs.com/yintoki/p/5705292.html