61
zoj 2750 Idiomatic Phrases Game 最短路
一个预处理比较累的最短路，要先生成边，编码是16进制，一开始写成10进制一直WA……
/*
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 <queue>
#include <vector>
#define pp pair<int,int>
#define INF 1E9
using namespace std;
int ff[65536];//对于首位的存储，便于生成边
int fn[1001];//拉链法解决冲突
int org[1001],vn[1001];//org是前4位的地址代码 vn是边权值
int first[1001];
int next[1000001];//邻接表 可能退化到n^2
int u[1000001];//边的指向
int n,cnt;
int turn(char *s)//hash函数
{
int h=0,i;
for(i=0;i<4;i++)
{
h*=16;
if(s[i]>'9')h+=s[i]-'A'+10;
else h+=s[i]-'0';
}
return h;
}
int d[1002];
int dijkstra(int v)
{
priority_queue<pp,vector<pp>,greater<pp> > q;
memset(d,127,sizeof(d));
d[v]=0;
q.push(make_pair(d[v],v));
pp now;
int x,i;
while(!q.empty())
{
now=q.top();q.pop();
x=now.second;
if(vn[x]==-1)continue;
for(i=first[x];i!=-1;i=next[i])
{
if(d[u[i]]<=d[x]+vn[x])continue;
d[u[i]]=d[x]+vn[x];
q.push(make_pair(d[u[i]],u[i]));
}
vn[x]=-1;
}
// cout<<d[1001]<<endl;
return d[n-1]==d[1001]?-1:d[n-1];
}
char s[100];
int main()
{
int i,t,tt,hf,hl;
while(~scanf("%d",&n)&&n)
{
memset(ff,-1,sizeof(ff));
memset(fn,-1,sizeof(fn));
memset(first,-1,sizeof(first));
memset(next,-1,sizeof(next));
cnt=0;
for(i=0;i<n;i++)
{
scanf("%d %s",&t,s);
hf=turn(s);
hl=turn(s+strlen(s)-4);
if(ff[hf]!=-1) fn[i]=ff[hf];
ff[hf]=i;
org[i]=hl;
vn[i]=t;
}
for(i=0;i<n;i++)
{
if(ff[org[i]]==-1)continue;
tt=ff[org[i]];
while(tt!=-1)
{
if(first[i]!=-1)
next[cnt]=first[i];
u[cnt]=tt;
first[i]=cnt++;
tt=fn[tt];
}
}
//cout<<"ok"<<endl;
printf("%d\n",dijkstra(0));
}
}
最后更新：2017-04-04 07:03:44