P4524 [COCI2017-2018 Contest4] Ceste

2018-11-06 17:45:15


题意:一个无向图,每条边有两个参数 $t$ 和 $c$ ,定义一条路径的长度为其上 $t$ 之和与 $c$ 之和的乘积,求点 $1$ 到其他点的最短路,不连通输出 $-1$


用了一下午终于过了~太感人了

最短路当然要用 $Dijkstra$ 了

但是怎么维护 $t$ 之和与 $c$ 之和的乘积呢~ 陷入沉思

经过百折不挠的思考和求助

得到正解:

用 $Dijkstra$ ,堆里面按照 $t \times c$ 的大小排序

这里的 $t$ 和 $c$ 就是一条路径上的 $t$ 和 $c$ 之和

再对每个点维护一个 $set$ ,记录到这个点时的 $t$ 和 $c$

以 $t$ 为第一关键字, $c$ 为第二关键字排序

最短路过程中判断是否可行即可

感谢 $@TimeTraveller$ 大佬对蒟蒻的帮助!

我为什么这么菜


如果你在 $2018.11.10$ 之前看到了这篇题解

那么~  $NOIP2018$   $rp++$ !

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<set>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=2005;
struct E
{
    int to,nxt,d1,d2;
}edge[N<<1];
struct node
{
    int x; ll t,c;
    inline friend bool operator < (node a,node b) {return a.t*a.c>b.t*b.c;}
};
struct snode
{
    ll t,c;
    inline friend bool operator < (snode a,snode b) {return a.t==b.t?a.c<b.c:a.t<b.t;}
};
int n,m,num,cnt=1,head[N],f[N],vis[N],tcnt;
ll ans[N];
priority_queue<node>q;
set<snode>S[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to,int d1,int d2)
{
    edge[++num]=(E){to,head[from],d1,d2};
    head[from]=num;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline bool check(int x,snode u)
{
    set<snode>::iterator i;
    for (i=S[x].lower_bound(u);i!=S[x].end()&&i->c>=u.c;i++) S[x].erase(i);
    if (i!=S[x].begin()) {--i; if (i->c<u.c) return 0;}
    S[x].insert(u); return 1;
}
inline void Dijkstra(int s)
{
    q.push((node){s,0,0});
    while (!q.empty())
    {
        node u=q.top(); q.pop();
        if (!check(u.x,(snode){u.t,u.c})) continue;
        if (!vis[u.x]) vis[u.x]=1,ans[u.x]=u.t*u.c,++tcnt;
        if (tcnt==cnt) return;
        for (reg int i=head[u.x];i;i=edge[i].nxt)
        {
            int v=edge[i].to,t=edge[i].d1,c=edge[i].d2;
            q.push((node){v,u.t+t,u.c+c});
        }
    }
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=n;i++) f[i]=i,ans[i]=-1;
    for (reg int i=1;i<=m;i++)
    {
        int a=read(),b=read(),c=read(),d=read();
        add_edge(a,b,c,d); add_edge(b,a,c,d);
        if (find(a)!=find(b)) f[f[a]]=f[b];
    }
    for (reg int i=2,rt=find(1);i<=n;i++) if (find(i)==rt) ++cnt;
    Dijkstra(1);
    for (reg int i=2;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}