2021 robocom 机器人大赛初赛 C

题意: 给定n(n<=100)个点，m条无向边有边权1和边权2。任务1. 求一个点，它到其他点的最短路的最大值最小。任务2. 用这个点跑最短路，保存路径。如果边权1的最短路有多条，记录边权2更大的路径。
思路: 给了5s，而且pta可以骗分。任务1用Floyd跑即可，之后任务2用朴素Dij跑，记得记录路径即可。但是为什么我用堆优化的Dij反而wa两个点，有懂哥知道可以跟我一说。

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i<=b;++i) 
#define mem(a,x) memset(a,x,sizeof(a))
#define p_ priority_queue
// round() 四舍五入 ceil() 向上取整 floor() 向下取整
// lower_bound(a.begin(),a.end(),tmp,greater()) 第一个小于等于的
// #define int long long //QAQ
using namespace std;
typedef complex CP;
typedef pair PII;
typedef long long ll;
// typedef __int128 it;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const int N = 1e3+10;
const int M = 4e6+10;
const int mod = 1e9+7;
const double eps = 1e-6;
inline int lowbit(int x){ return x&(-x);}
templatevoid write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}
template void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
#define int long long
int n,m,k,T;
int h[N],e[M],ne[M],w[M],w2[M],idx = 0;
void add(int a,int b,int c,int d)
{
	e[idx] = b,w[idx] = c,w2[idx] = d,ne[idx] = h[a],h[a] = idx++;
}
int va[N];
int dist[N];
int dist2[N];
bool vis[N];
int pre[N];
void Dij2(int S)
{
   mem(pre,-1);
   mem(dist,0x3f);
   mem(dist2,-0x3f);
   mem(vis,false);
   dist[S] = 0;
   dist2[S] = 0;
   for(int t=0;t dist[idx] + w[i])
   	 	{
   	 		dist[j] = dist[idx] + w[i];
   	 		dist2[j] = dist2[idx] + w2[i];
   	 		pre[j] = idx;
   	 	}
   	 	if(!vis[j] && dist[j] == dist[idx] + w[i])
   	 	{
   	 		if(dist2[j] < dist2[idx] + w2[i])
   	 		{
   	 			pre[j] = idx;
   	 			dist2[j] = dist2[idx] + w2[i];
   	 		}
   	 	}
   	 }
   }
}
void Dij(int S)
{
   mem(pre,-1);
   mem(dist,0x3f);
   mem(dist2,-0x3f);
   mem(vis,false);
   priority_queue q;
   dist[S] = 0;
   dist2[S] = 0;
   q.push({0,S});
   while(q.size())
   {
   	 auto tmp = q.top(); q.pop();
   	 int u = tmp.second;
   	 if(vis[u]) continue;
   	 vis[u] = true;
   	 for(int i=h[u];~i;i=ne[i])
   	 {
   	 	int j = e[i];
   	 	if(dist[j] > dist[u] + w[i])
   	 	{
   	 		dist[j] = dist[u] + w[i];
   	 		q.push({dist[j],j});
   	 		pre[j] = u;
   	 		dist2[j] = dist2[u] + w2[i];
   	 	}
   	 	else if(dist[j] == dist[u] + w[i])
   	 	{
   	 		if(dist2[j] < dist2[u] + w2[i])
   	 		{
   	 			dist2[j] = dist2[u] + w2[i];
   	 			pre[j] = u;
   	 		}
   	 	}
   	 }
   }
}
int a[1002][1002];
int f[1002][1002];
void floyd()
{
   	for(int k=1;k<=n;++k)
   	{
   		for(int i=1;i<=n;++i)
   		{
   			for(int j=1;j<=n;++j)
   			{
   				a[i][j] = min(a[i][j],a[i][k]+a[k][j]);
   			}
   		}
   	}
}
void solve()
{
   mem(h,-1); idx = 0;
   read(n); read(m);
   for(int i=1;i<=n;++i)
   {
   	 for(int j=1;j<=n;++j)
   	 {
   	 	if(i == j) a[i][j] = 0;
   	 	else a[i][j] = INF;
   	 }
   }
   for(int i=0;i res;
   	 while(to != -1)
   	 {
   	 	res.push_back(to);
   	 	to = pre[to];
   	 }
   	 reverse(res.begin(),res.end());
   	 for(int i=0;i");
   	 	printf("%lld",res[i]);
   	 }
   	 puts("");
   	 printf("%lld %lldn",dist[to2],dist2[to2]);
   	 // puts("");
   }
}
signed main(void)
{  
   T = 1;
   // OldTomato; cin>>T;
   // read(T);
   while(T--)
   {
   	 solve();
   }
   return 0;
}

2021 robocom 机器人大赛 初赛 C

C/C++/C#相关栏目本月热门文章

2021 robocom 机器人大赛初赛 C