Planets

http://codeforces.com/contest/230/problem/D

解题思路：求最短路，如果到了那个在t时刻到了i点 且有人的话，就dis++；

spfa 求解， 用了set ，vector，queue ，fill 加强了对c++函数的学习。

基于spfa的：
View Code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define inf ~0U>>1
using namespace std;
const int maxn=100005;
typedef pair<int,int>pii;
vector< pii>node[maxn];
set<int>time[maxn];
queue< pii> q;
int dis[maxn];
int visit[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        node[a].push_back(pii(b,c));
        node[b].push_back(pii(a,c));
    }
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d",&k);
        while(k--)
        {
            int t;
            scanf("%d",&t);
            time[i].insert(t);
        }
    }
    q.push(pii(0,1));
    fill(dis,dis+n+1,inf);
    dis[1]=0;
    visit[1]=1;

    while(!q.empty())
    {

        int mm=q.front().second;
        q.pop();
        while(mm<n&&time[mm].count(dis[mm]))dis[mm]++;
        for(int i=0;i<node[mm].size();i++)
        {
            int u=node[mm][i].first;
            int t=node[mm][i].second;
            if(dis[u]>dis[mm]+t)
            {
                dis[u]=dis[mm]+t;
                if(!visit[u])
                {
                    visit[u]=1;
                    q.push(pii(dis[u],u));
                }
            }
        }
        visit[mm]=0;
    }
    printf("%dn",dis[n]==inf?-1:dis[n]);
    return 0;
}

基于dijkstra的：
View Code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define inf ~0U>>1
using namespace std;
const int maxn=100005;
typedef pair<int,int>pii;
vector< pii>node[maxn];
set<int>time[maxn];
priority_queue< pii> q;
int dis[maxn];
int visit[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        node[a].push_back(pii(b,c));
        node[b].push_back(pii(a,c));
    }
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d",&k);
        while(k--)
        {
            int t;
            scanf("%d",&t);
            time[i].insert(t);
        }
    }
    q.push(pii(0,1));
    fill(dis,dis+n+1,inf);
    dis[1]=0;
    while(!q.empty())
    {

        int mm=q.top().second;
        q.pop();
        if(visit[mm])continue;
        visit[mm]=1;
        //cout<<mm<<endl;
        while(mm<n&&time[mm].count(dis[mm]))dis[mm]++;
        for(int i=0;i<node[mm].size();i++)
        {
            int u=node[mm][i].first;
            int t=node[mm][i].second;
            if(!visit[u]&&dis[u]>dis[mm]+t)
            {
                dis[u]=dis[mm]+t;
                q.push(pii(-dis[u],u));

            }
        }

    }
    printf("%dn",dis[n]==inf?-1:dis[n]);
    return 0;
}

原文链接: https://www.cnblogs.com/cs1003/archive/2012/10/02/2710428.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍