题意:
给一个城市网络,有n*m个街区组成,每条路所花时间易求,要算从城市左上角到右下叫的最短时间。
分析:
简单最短路,只是输入有点恶心。
代码:
//poj 3653
//sepNINE
#include <iostream>
#include <queue>
using namespace std;
const int maxN=512;
const int maxM=2048;
int n,m,e,head[maxN],inq[maxN],d[maxN];
struct Edge
{int v,w,next;
}edge[maxM];
void addEdge(int u,int v,int w)
{edge[e].v=v;edge[e].w=2520/w;edge[e].next=head[u];head[u]=e++;
}void spfa()
{int i;queue<int> Q;for(i=0;i<n;++i) d[i]=INT_MAX;inq[0]=1;d[0]=0;Q.push(0);while(!Q.empty()){int u=Q.front();Q.pop();inq[u]=0;for(i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v,w=edge[i].w; if(d[v]>d[u]+w){d[v]=d[u]+w;if(!inq[v]){inq[v]=1;Q.push(v);} } } }if(d[n-1]==INT_MAX)printf("Holiday\n");elseprintf("%d blips\n",d[n-1]);
}int main()
{while(scanf("%d%d",&n,&m)==2&&n){e=0;memset(head,-1,sizeof(head));memset(inq,0,sizeof(inq));int i,j,x;char tmp[8],c;for(i=0;i<2*n+1;++i){if(i%2==0)for(j=0;j<m;++j){scanf("%d%s",&x,tmp); c=tmp[0];int u=i/2*(m+1)+j;int v=i/2*(m+1)+j+1;if(x==0)continue;else if(c=='*'){addEdge(u,v,x);addEdge(v,u,x);}else if(c=='>')addEdge(u,v,x);else if(c=='<')addEdge(v,u,x);}elsefor(j=0;j<m+1;++j){scanf("%d%s",&x,tmp);c=tmp[0];int u=(i/2)*(m+1)+j;int v=(i/2+1)*(m+1)+j;if(x==0)continue;else if(c=='*'){addEdge(u,v,x);addEdge(v,u,x);}else if(c=='v')addEdge(u,v,x);else if(c=='^')addEdge(v,u,x);}} n=(n+1)*(m+1); spfa(); } return 0;
}