P4524 [COCI2017-2018 Contest4] Ceste

题意：一个无向图，每条边有两个参数$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; } ```