poj 1613 Cave Raider 最短路

很简单的最短路，只是加上了一定的限制条件。

        首先读取时做下处理，把开放时间小于通行时间的去掉。

        做最短路的时候判断好逻辑关系即可

        注意，这题输入有问题，可能行尾有空格之类的

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1E9
using namespace std;
int N,M,S,T;
int U[1001];
int W[1001];
int next[1001];
int first[51];
vector<int> so[1001];
vector<int>::iterator bi;
int cnt=0;
int t;
char st;
void add(int v,int u,int w)
{
    next[cnt]=first[v];//双向边
    first[v]=cnt;
    U[cnt]=u;
    W[cnt]=w;
    so[cnt].clear();

    next[cnt+1]=first[u];
    first[u]=cnt+1;
    U[cnt+1]=v;
    W[cnt+1]=w;
    so[cnt+1].clear();

    while(1)
    {
        while(st=getchar())
        {
            if(isdigit(st)||st=='\n')
            {
                ungetc(st,stdin);
                break;
            }
        }
        if(st=='\n')break;
        scanf("%d",&t);
        so[cnt].push_back(t);
        so[cnt+1].push_back(t);
        //如果一次开启到关闭的时间小于路途需要时间则直接pop掉
        t=so[cnt].size();
        int b,e;
        if(t>1&&t%2)
        {
            e=t-1;
            b=e-1;
            if(so[cnt][e]-so[cnt][b]<W[cnt])
            {
                so[cnt].pop_back();
                so[cnt].pop_back();
                so[cnt+1].pop_back();
                so[cnt+1].pop_back();
            }
        }

    }
    cnt+=2;
}
bool inq[51];
int Dis[52];
queue<int> q;

int spfa()
{
    int i,v,u,now;
    memset(inq,0,sizeof(inq));
    for(i=0;i<=N;i++)Dis[i]=INF;
    Dis[S]=0;
    q.push(S);
    while(!q.empty())
    {
        v=q.front();q.pop();
        inq[v]=0;
        now=Dis[v];
        for(i=first[v];i!=-1;i=next[i])
        {
            u=U[i];t=0;
            bi=lower_bound(so[i].begin(),so[i].end(),now);//确定之前经历了几次开关操作
            int b=bi-so[i].begin(),l=so[i].size();
            if(b==l)
            {
                if(l%2)t=INF;
                else t=now+W[i];
            }
            else
            {
                if(b%2==0)
                {
                    if(so[i][b]-now>=W[i])//现在为开放，则判断现在时间距关闭时间能否通行
                        t=now+W[i];
                    else b++;//否则就等待下次开放
                }
                if(!t)
                {
                    if(b==l)t=INF;
                    else t=so[i][b]+W[i];
                }
            }
            if(Dis[u]<=t)continue;
            Dis[u]=t;
            if(inq[u])continue;
            inq[u]=1;
            q.push(u);
        }
    }
    return Dis[T]==INF?-1:Dis[T];
}
int main()
{
    while(~scanf("%d",&N)&&N)
    {
        scanf("%d%d%d",&M,&S,&T);
        memset(first,-1,sizeof(first));
        int v,u,w,i;
        cnt=0;
        for(i=0;i<M;i++)
        {
            scanf("%d%d%d",&v,&u,&w);
            add(v,u,w);
        }
        t=spfa();
        if(t!=-1)printf("%d\n",t);
        else puts("*");
    }
}