POJ3653HereWeGo(relians)Again(最短路)

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

题意：给定(n+1)*(m+1)个点，在构成的有向图中，每条边的值为极限速度，每段边长度为LEN,求从起点到终点的最短距离。

思路：没什么技巧，就是最短路算法，把二维点hash到一维就可以了n*k+m，输入时还是需要注意一些小细节，由于数据量不大，O(n^2)的dij就可以，16ms，用priority_queue优化就可以0ms了。

O(nlgn):


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
using namespace std;

const int BORDER = (1<<20)-1;
const int MAXSIZE = 37;
const int MAXN = 1105;
const int INF = 1000000000;
#define CLR(x,y) memset(x,y,sizeof(x))
#define ADD(x) x=((x+1)&BORDER)
#define IN(x) scanf("%d",&x)
#define OUT(x) printf("%d\n",x)
#define MIN(m,v) (m)<(v)?(m):(v)
#define MAX(m,v) (m)>(v)?(m):(v)
#define ABS(x) ((x)>0?(x):-(x))

#define LEN 2520
#define SET_NODE(no,a,b) {no.u=a;no.val=b;}

typedef struct{
int v,next;
int val;
}Edge;
typedef struct{
int u;
int val;
}Node;
bool operator < (const Node& a,const Node& b)
{
return a.val > b.val;
}

Edge edge[MAXN*MAXN];
int n,m,start,end,index;
int dist[MAXN],net[MAXN];
bool visit[MAXN];

void add_edge(const int& u,const int& v,const int& sp)
{
    edge[index].v = v;
    edge[index].next = net[u];
    edge[index].val = sp;
    net[u] = index++;
}
void add_input(const int& u,const int& v,const int& sp,const char& c)
{
if(c=='*')
    {
        add_edge(u,v,sp);
        add_edge(v,u,sp);
return ;
    }
if( c == '>' || c=='v')
        add_edge(u,v,sp);
else
        add_edge(v,u,sp);
}
int init()
{
    index = 0;
    CLR(net,-1);
    CLR(visit,0);
    CLR(dist,127);
return 0;
}
int input()
{
int i,j,u,v,tmp,sp;
char ch;
for(i = 0; i < n-1; ++i)
    {
for(j = 0; j < m-1; ++j)
        {
            scanf("%d %c",&sp,&ch);
if(sp == 0)
continue;
            u = i*m + j;
            v = u + 1;
            add_input(u,v,sp,ch);
        }
for(j = 0; j < m; ++j)
        {
            scanf("%d %c",&sp,&ch);
if(sp == 0)
continue;
            u = i*m + j;
            v = (i+1)*m + j;
            add_input(u,v,sp,ch);
        }
    }
for(j = 0; j < m-1; ++j)
    {
        scanf("%d %c",&sp,&ch);
        u = (n-1)*m + j;
        v = u + 1;
if(sp == 0)
continue;
        add_input(u,v,sp,ch);
    }
return 0;
}
int dij()
{
int i,j,u,tmp,mark,mmin,v;
int N = n*m;
    priority_queue<Node> que;
    Node node,t_node;
while(!que.empty())
        que.pop();
    SET_NODE(t_node,0,0);
    que.push(t_node);
    dist[0] = 0;
    CLR(visit,0);
while(!que.empty())
    {
        node = que.top();
        que.pop();
        u = node.u;
if(visit[node.u])
continue;
if(u == N-1)
return node.val;
        visit[u] = true;
for(i = net[u]; i != -1; i = edge[i].next)
        {
            v = edge[i].v;
if(visit[v])
continue;
            tmp = dist[u] + LEN/edge[i].val;
if(dist[v] > tmp)
            {
                dist[v] = tmp;
                SET_NODE(t_node,v,tmp);
                que.push(t_node);
            }
        }
    }
return -1;
}
int work()
{
int i,j,ans;
    ans = dij();
if(ans == -1)
        printf("Holiday\n");
else
         printf("%d blips\n",ans);
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m))
    {
if(!n && !m)
break;
++n,++m;
        init();
        input();
        work();
    }
return 0;
}

O(n^2):


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
using namespace std;

const int BORDER = (1<<20)-1;
const int MAXSIZE = 37;
const int MAXN = 1105;
const int INF = 1000000000;
#define CLR(x,y) memset(x,y,sizeof(x))
#define ADD(x) x=((x+1)&BORDER)
#define IN(x) scanf("%d",&x)
#define OUT(x) printf("%d\n",x)
#define MIN(m,v) (m)<(v)?(m):(v)
#define MAX(m,v) (m)>(v)?(m):(v)
#define ABS(x) ((x)>0?(x):-(x))

#define LEN 2520

typedef struct{
int v,next;
int val;
}Edge;
typedef struct{
int u;
int val;
}Node;
bool operator < (const Node& a,const Node& b)
{
return a.val > b.val;
}

Edge edge[MAXN*MAXN];
int n,m,start,end,index;
int dist[MAXN],net[MAXN];
bool visit[MAXN];

void add_edge(const int& u,const int& v,const int& sp)
{
    edge[index].v = v;
    edge[index].next = net[u];
    edge[index].val = sp;
    net[u] = index++;
}
void add_input(const int& u,const int& v,const int& sp,const char& c)
{
if(c=='*')
    {
        add_edge(u,v,sp);
        add_edge(v,u,sp);
return ;
    }
if( c == '>' || c=='v')
        add_edge(u,v,sp);
else
        add_edge(v,u,sp);
}
int init()
{
    index = 0;
    CLR(net,-1);
    CLR(visit,0);
    CLR(dist,127);
return 0;
}
int input()
{
int i,j,u,v,tmp,sp;
char ch;
for(i = 0; i < n-1; ++i)
    {
for(j = 0; j < m-1; ++j)
        {
//cin>>sp>>ch;
            scanf("%d %c",&sp,&ch);
if(sp == 0)
continue;
            u = i*m + j;
            v = u + 1;
            add_input(u,v,sp,ch);
        }
for(j = 0; j < m; ++j)
        {
//cin>>sp>>ch;
            scanf("%d %c",&sp,&ch);
if(sp == 0)
continue;
            u = i*m + j;
            v = (i+1)*m + j;
            add_input(u,v,sp,ch);
        }
    }
for(j = 0; j < m-1; ++j)
    {
//cin>>sp>>ch;
        scanf("%d %c",&sp,&ch);
        u = (n-1)*m + j;
        v = u + 1;
if(sp == 0)
continue;
        add_input(u,v,sp,ch);
    }
return 0;
}
int dij()
{
int i,j,tmp,mark,mmin,v;
int N = n*m;
    dist[0] = 0;
    CLR(visit,0);
for(i = 0; i < N; ++i)
    {
        mmin = INF;
for(j = 0; j < N; ++j)
if(!visit[j] && mmin > dist[j])
            {
                mmin = dist[j];
                mark = j;
            }
        visit[mark] = true;
for(j = net[mark]; j != -1; j = edge[j].next)
        {
            tmp = LEN/edge[j].val;
            v = edge[j].v;
if(!visit[v] && dist[v] > tmp + mmin)
            {
                dist[v] = tmp + mmin;
            }
        }
    }
if(dist[N-1] > INF)
return -1;
return dist[N-1];
}
int work()
{
int i,j,ans;
    ans = dij();
if(ans == -1)
        printf("Holiday\n");
else
         printf("%d blips\n",ans);
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m))
    {
if(!n && !m)
break;
++n,++m;
        init();
        input();
        work();
    }
return 0;
}