absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] 101630G

[破碎的状态] 101630J

absi2011 posted @ Mar 02, 2018 01:44:32 PM in 刷题记录 with tags 小高考 CF dijkstra Gym , 1197 阅读

感谢@wavator 提供解题思路!

题意:

n个点m条边的图

求1到n的最短路

PS:路径长度只计算路径上长度最大的k条边

n<=3000 m<=3000 k<=m

解法:

每次我们枚举最小值,然后做dijkstra

dijkstra的时候,我们让所有边的长度减t(负的按0计),最后答案再加t*k

这样,我们可以保证:

对于t是最小值,如果没走满k条边,那么答案肯定会更劣(因为我们多加了t*k,理论上应该是t*边数)

如果走满了k条边的话,如果是k条边以上,答案肯定没有最小值更大的优

所以这样就可以求得最小值

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long dist[3005];
struct edge
{
    int y;
    int weight;
    edge * next;
};
edge * new_edge()
{
    static edge a[6005];
    static int top=0;
    return &a[top++];
}
edge * li[3005];
void inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    t->weight=z;
    li[x]=t;
}
void insert_edge(int x,int y,int z)
{
    inserts(x,y,z);
    inserts(y,x,z);
}
int w[3005];
int k;
int n;
long long ans=1999999999999999999ll;
bool vis[3005];
void dijkstra(int w)
{
    memset(dist,-1,sizeof(dist));
    memset(vis,false,sizeof(vis));
    dist[0]=0;
    priority_queue<pair<long long,int> > q;
    q.push(make_pair(0,0));
    for (;!q.empty();)
    {
        int now=q.top().second;
        q.pop();
        if (vis[now]) continue;
        vis[now]=true;
        edge * t;
        for (t=li[now];t!=0;t=t->next)
        {
            if ((dist[t->y]==-1)||(dist[t->y]>dist[now]+max(0,t->weight-w)))
            {
                dist[t->y]=dist[now]+max(0,t->weight-w);
                q.push(make_pair(-dist[t->y],t->y));
            }
        }
    }
    if (dist[n-1]==-1) return;
    ans=min(ans,dist[n-1]+(long long)w*k);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int m;
    scanf("%d%d%d",&n,&m,&k);
    int i;
    for (i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d%d",&x,&y,&w[i]);
        x--;
        y--;
        insert_edge(x,y,w[i]);
    }
    dijkstra(0);
    for (i=0;i<m;i++)
    {
        dijkstra(w[i]);
    }
    cout<<ans<<endl;
    return 0;
}

 

Wavator 说:
Apr 26, 2018 12:39:39 AM

啊可是Wavator这么菜一个月之后才看到

Comprar seguidores 说:
Sep 02, 2020 08:37:16 PM

Eu me pergunto como você ficou tão bom. HaHa! Este é realmente um blog fascinante, muitas coisas em que posso me aprofundar. Só quero dizer que seu design é tão perfeito!

GSEB 11th Previous P 说:
Aug 22, 2022 04:05:06 AM

This year's GSEB Class Xllth Exams were administered by the Gujarat Secondary and Higher Secondary Education Board. upon the satisfactory completion of the exam. The GSEB Class 11th Examination Question Paper 2023 will be released by the Gujarat Board in the month of May. The Gujarat Board offers students a better education. GSEB 11th Previous Paper 2023 those those who are taking the Gujarat Board Plus-1 Exams. They are all impatiently awaiting the release of the 2023 Gujarat Board +1 Question Paper online. The Gujarat Board 11th Important Question Paper 2023 may be downloaded from the official website, and we also give a direct link so you can quickly check your Gujarat 11th Important Question Paper 2023. Listed below are some helpful instructions for students; all you have to do is adhere to them.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter