题目传送门：https://uva.onlinejudge.org/index.php?problem=3468
中文题面：《算法竞赛·入门经典·训练指南》P331
一直以为是一个建图非常神奇的最短路/网络流
然而居然是类似斯坦纳树一样的转移怪异的DP
设d[i]为满足题目条件的情况下，到达第i个点时的最少货物量
然后反向各更新即可
更新的方式的话，显然SPFA的正确性没有问题
又因为没有负权，所以Dijkstra也是正确的？
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 70;
const int M = 2000+9;
const double EPS = 1e-4;
int head[N],nxt[M],to[M],m,T,MN,s,t,case_cnt;
LL d[N]; bool inq[N]; queue<int> que;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline int ID(const char c) {
if ('a' <= c && c <= 'z') return c - 'a' + 1;
else return c - 'A' + 27;
}
inline void Add_Edge(int u, int v) {
to[++T] = v; nxt[T] = head[u]; head[u] = T;
to[++T] = u; nxt[T] = head[v]; head[v] = T;
}
inline LL cost(int w, LL val) {
if (w == s) return 0;
else if (w <= 26) return 1;
else {
LL l=1,r=1e15,ret=1,mid;
while (l <= r) {
mid = l + r >> 1;
if (val+mid-(LL)(ceil((val+mid)/20.0)+EPS) >= val) ret = mid, r = mid - 1;
else l = mid+1;
}
return ret;
}
}
inline LL SPFA() {
memset(d,0x3f,sizeof(d));
d[t] = MN + (s!=t?cost(t, MN):0);
inq[t] = 1; que.push(t);
while (!que.empty()) {
int w = que.front(); inq[w] = 0; que.pop();
for (int i=head[w];i;i=nxt[i]) {
if (d[to[i]] > d[w] + cost(to[i],d[w])) {
d[to[i]] = d[w] + cost(to[i],d[w]);
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return d[s];
}
int main(){
static char U[10],V[10];
for (m=read();~m;m=read(),T=0) {
memset(head,0,sizeof(head));
for (int i=1;i<=m;i++) {
scanf("%s %s",U+1,V+1);
Add_Edge(ID(U[1]), ID(V[1]));
}
MN = read();
scanf("%s %s",U+1,V+1);
s = ID(U[1]); t = ID(V[1]);
printf("Case %d: %lld\n",++case_cnt,SPFA());
}
return 0;
}
哇塞，居然是沙发？留个名
I pay a quick visit day-to-day a few sites and sites to read articles or reviews,
but this webpage presents quality based writing.
Ahaa, its pleasant conversation on the topic of this piece of writing
here at this web site, I have read all that, so now me also commenting here.
Thank you for any other informative blog.
The place else may I am getting that type of info written in such a
perfect manner? I’ve a mission that I am simply now operating on, and I have been at the glance out for such info.
Hi to every one, the contents existing at this web site are
in fact amazing for people experience, well, keep up the good work fellows.
Great work! This is the type of info that are meant to
be shared around the internet. Shame on Google for no longer positioning
this post higher! Come on over and visit my site . Thank you =)
Hmm is anyone else encountering problems with the images on this blog loading?
I’m trying to figure out if its a problem on my end or if it’s the blog.
Any feed-back would be greatly appreciated.
It’s difficult to find knowledgeable people about this topic, but you seem like
you know what you’re talking about! Thanks
Hey! This post could not be written any better! Reading through this post reminds me of my good old room mate!
He always kept chatting about this. I will forward this article to him.
Pretty sure he will have a good read. Thank you for sharing!
Does your site have a contact page? I’m having a
tough time locating it but, I’d like to shoot you an email.
I’ve got some ideas for your blog you might be interested in hearing.
Either way, great website and I look forward to seeing it improve over time.
This page really has all of the info I needed concerning
this subject and didn’t know who to ask.
Hi there, I enjoy reading all of your article. I like to write a
little comment to support you.
Hello, i read your blog occasionally and i own a similar one and i was just wondering if you get a lot of spam feedback? If so how do you stop it, any plugin or anything you can advise? I get so much lately it’s driving me crazy so any support is very much appreciated.
It’s fantastic that you are getting ideas from this post as
well as from our discussion made here.
I love what you guys are usually up too. This kind of clever work and exposure!
Keep up the superb works guys I’ve included
you guys to blogroll.
You actually make it seem so easy along with your presentation but I find this matter to be actually something which
I believe I’d by no means understand. It sort of feels too complex and very broad for me.
I am taking a look forward for your subsequent submit, I’ll attempt
to get the hang of it!
We are a bunch of volunteers and opening a new scheme in our community.
Your web site offered us with useful information to work on. You’ve done an impressive activity and our whole group will likely be grateful to
you.
Nice weblog right here! Additionally your website loads up very fast!
What web host are you the use of? Can I get your associate hyperlink for
your host? I want my web site loaded up as fast as yours lol
Everyone loves it when individuals get together and share ideas.
Great website, stick with it!
First off I would like to say fantastic blog! I had a quick question which
I’d like to ask if you do not mind. I was interested to find out
how you center yourself and clear your thoughts prior to writing.
I’ve had trouble clearing my thoughts in getting my ideas out.
I do take pleasure in writing however it just seems like the first 10 to 15 minutes are usually wasted just trying to figure out how to begin. Any suggestions or
hints? Appreciate it!
Hey there! I know this is somewhat off topic but I was wondering if you knew where I could find a captcha
plugin for my comment form? I’m using the same blog platform as yours and I’m
having trouble finding one? Thanks a lot!
Fine way of explaining, and fastidious piece of writing to obtain data regarding my presentation subject, which
i am going to convey in academy.
Terrific article! That is the kind of info that are meant to be shared across the net.
Disgrace on Google for no longer positioning this publish upper!
Come on over and consult with my site . Thanks =)
Pretty portion of content. I simply stumbled upon your blog and in accession capital
to assert that I get actually enjoyed account your blog posts.
Anyway I will be subscribing for your feeds and even I success you access consistently
fast.
Hello to all, the contents present at this site are actually awesome for people experience,
well, keep up the good work fellows.
Its like you read my thoughts! You seem to grasp a lot
approximately this, like you wrote the e-book in it or something.
I feel that you just can do with a few percent to drive the message home a bit, however other than that,
this is wonderful blog. An excellent read.
I’ll certainly be back.
I loved as much as you’ll receive carried out right here. The sketch is
tasteful, your authored subject matter stylish.
nonetheless, you command get got an impatience over that you wish be delivering the
following. unwell unquestionably come more formerly again since exactly the
same nearly a lot often inside case you shield this increase.
Thank you for the auspicious writeup. It in reality
was a amusement account it. Look advanced to far delivered agreeable
from you! However, how can we keep up a correspondence?
Magnificent site. Lots of useful info here. I’m sending it to some friends ans also sharing in delicious. And naturally, thanks for your sweat!