Intermediary
时间： 1ms 内存：128M
描述：
It is widely known that any two strangers can get to know each other through at most six other people. Now let’s prove this.
In the country Intermediary Conducts Personal Communications (ICPC), there are up to n (2<=n<=100) ordinary people conveniently numbered from 0 to n-1. They don’t know each other, or, in other words, they are strangers. The only way they can communicate with each other is through the government, which, in fact, is an intermediary agency. The government consists of up to m (1<=m<=9) employees conveniently numbered from 0 to m-1. Suppose employee z can introduce person x to person y at a cost of d dollars. If this is the first time in a day that employee z introduce one person to another, he will only require d dollars. For the second time, he will require d dollars plus extra e dollars as his tip. For the third time and more, he will require d dollars plus extra f dollars. He is not dared to require any more than that since the strange country is somewhat democratic. And if person x is able to communicate with person t and person t is able to communicate with person y, then person t is always willing to transfer messages from person x to person y, at no charge. Of course, the intermediary fees are all paid by person x. Notice that employee z being able to introduce person x to person y doesn’t mean he can introduce person y to person x.
Now person 0 has to send a message to person n-1 in one day. If all employees have just started to work, what is the minimum cost for person 0?
输入：
For each test case, the first line contains three integers, n, m and q, where q is the number of intermediary relationships and q is at most 10,000. The second line has m integers, each indicating the value e of every employee, in the range [0, 100]. The third line has m integers too, each indicating the value f of every employee, in the range [e, 200]. The next q lines each contains four integers, x, y, z and d, indicating that employee z can introduce person x to person y requiring d dollars, where 1<=d<=200. There is a blank line after each test case.
Proceed to the end of file.
输出：
For each test case, print one integer on a single line, giving the minimum cost. If it is impossible, print -1.
示例输入：
3 2 2
1 1
2 2
0 1 0 1
1 2 1 2
5 1 4
1
2
0 1 0 1
1 2 0 1
2 3 0 1
3 4 0 1示例输出：
3
9提示：
参考答案（内存最优[26348]）：
#include<cstring>
#include<cstdio>
#define __FILE_GENERATOR__
struct Edge
{
int m,w,l;
Edge *next;
};
int const INF=0x3fffffff;
int const N=100,M=9,Q=10000;
int const S=2000000;
int p3[M+1];
Edge edges[Q];
Edge *adj[N];
int e[M],f[M];
int ii[S],jj[S];
int d[S];
bool b[S];
int n,m,q;
int cnt,num;
inline void initialize()
{
int k;
p3[0]=1;
for(k=1;k<=M;++k)
p3[k]=p3[k-1]*3;
}
inline Edge* makeEdge(int m,int w,int l,Edge *next)
{
edges[cnt].m=m;
edges[cnt].w=w;
edges[cnt].l=l;
edges[cnt].next=next;
return &edges[cnt];
}
bool readin()
{
int x,y,z,d,k;
if(scanf("%d%d%d",&n,&m,&q)==EOF)
return false;
for(k=0;k<m;++k)
scanf("%d",&e[k]);
for(k=0;k<m;++k)
scanf("%d",&f[k]);
for(k=0;k<n;++k)
adj[k]=NULL;
for(cnt=0;cnt<q;++cnt)
{
scanf("%d%d%d%d",&x,&y,&z,&d);
adj[x]=makeEdge(z,y,d,adj[x]);
}
return true;
}
inline int D(int index)
{
return d[index];
}
void remove()
{
int x,y,z,r=1,pr,left,right;
z=ii[num];
ii[1]=z;
jj[z]=1;
--num;
while((r<<1)<=num)
{
left=r<<1;
right=(r<<1)+1;
if(right<=num)
pr=D(ii[left])<D(ii[right])?left:right;
else
pr=left;
if(D(ii[r])<=D(ii[pr]))
break;
x=ii[r];
y=ii[pr];
ii[r]=y;
jj[y]=r;
ii[pr]=x;
jj[x]=pr;
r=pr;
}
}
void adjust(int pr)
{
int x,y,r;
while((pr>>1)>=1)
{
r=pr>>1;
if(D(ii[r])<=D(ii[pr]))
break;
x=ii[r];
y=ii[pr];
ii[r]=y;
jj[y]=r;
ii[pr]=x;
jj[x]=pr;
pr=r;
}
}
void solve()
{
int status,pstatus,nstatus,v,w,mid,t,l,k;
Edge *pE;
cnt=p3[m]*n;
for(k=0;k<cnt;++k)
{
d[k]=INF;
ii[k+1]=k;
jj[k]=k+1;
}
memset(b,false,sizeof(b));
num=cnt;
d[0]=0;
while(true)
{
if(num==0)
{
printf("-1\n");
return;
}
pstatus=ii[1];
if(d[pstatus]==INF)
{
printf("-1\n");
return;
}
b[pstatus]=true;
v=pstatus/p3[m];
status=pstatus%p3[m];
if(v==n-1)
{
printf("%d\n",d[pstatus]);
return;
}
pE=adj[v];
remove();
while(pE!=NULL)
{
mid=pE->m;
t=(status%p3[mid+1])/p3[mid];
w=pE->w;
l=pE->l;
if(t==0)
{
nstatus=status+p3[mid];
}
else if(t==1)
{
l+=e[mid];
nstatus=status+p3[mid];
}
else if(t==2)
{
l+=f[mid];
nstatus=status;
}
nstatus+=w*p3[m];
if(!b[nstatus]&&d[pstatus]+l<d[nstatus])
{
d[nstatus]=d[pstatus]+l;
adjust(jj[nstatus]);
}
pE=pE->next;
}
}
}
int main()
{
initialize();
while(readin())
solve();
return 0;
}
参考答案（时间最优[88]）：
#include <stdio.h>
#include <string.h>
#define N 10000
#define LEN 32
#define X 10010
struct Trie
{
int end;
int v;
struct Trie *son[26];
};
int n, nx;
int buf_cnt;
struct Trie *root, buf[N*LEN];
int max[X];
char x[X];
struct Trie* New_node()
{
struct Trie *tmp = &buf[buf_cnt++];
tmp->end = 0;
tmp->v = 0;
for (int i = 0; i < 26; i++)
tmp->son[i] = 0;
return tmp;
}
void insert(char *s, int v)
{
struct Trie *cur = root;
for (int i = 0; s[i] != 0; i++)
{
int id = s[i] - 'a';
if (cur->son[id] == NULL)
cur->son[id] = New_node();
cur = cur->son[id];
}
cur->end = 1;
cur->v = v;
}
void reversal(char *s)
{
int i = 0;
int j = strlen(s);
j--;
while (i < j)
{
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
}
}
void query(int i)
{
struct Trie *cur = root;
for (int j = i; x[j] != 0; j--)
{
int id = x[j] - 'a';
if (cur->son[id])
{
if (cur->son[id]->end)
{
if (max[j-1] != -1)
{
if (max[j-1]+cur->son[id]->v > max[i])
max[i] = max[j-1] + cur->son[id]->v;
}
}
cur = cur->son[id];
}
else
break;
}
}
int main()
{
//freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
x[0] = 0;
while (scanf("%d %s", &n, x+1) != EOF)
{
nx = strlen(x+1);
buf_cnt = 0;
root = New_node();
for (int i = 0; i < n; i++)
{
char s[LEN];
int v;
scanf("%s %d", s, &v);
reversal(s);
insert(s, v);
}
max[0] = 0;
for (int i = 1; i <= nx; i++)
{
max[i] = -1;
query(i);
}
printf("%d\n", max[nx]);
}
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。