题目列表
沙漠旅行
一道最短路模板。
q.push(make_pair(dis[v],v)); 写成 q.push(make_pair(w,v)); 痛失 $80pts$。
上述的时间复杂度是带 $\log$ 的，光 $\mathcal O(nm)$ 过不了，要堆优化。
在看完 std 的思路后焕然大悟，若全是边权为 $1$，bfs 跑一下即可。
这里边权最多为 $$
代码
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
struct node
{
int w,v;
};
priority_queue<pii,vector<pii>,greater<pii>>q;
int n,m;
vector<pii>a[300020];
int vis[300020];
int dis[300020];
void dij(int s)
{
memset(dis,0x3f,sizeof(dis));
q.push(make_pair(0,s));
dis[s]=0;
while(!q.empty())
{
while(!q.empty()&&vis[q.top().second])q.pop();
if(q.empty())break;
int u=q.top().second;
vis[u]=1;
// cout<<u<<endl;
q.pop();
for(auto i:a[u])
{
int w=i.first;
int v=i.second;
// printf("%d %d %d\n",u,v,w);
if(dis[u]+w<dis[v])
{
vis[i.first]=1;
dis[v]=dis[u]+w;
q.push(make_pair(w,v));
}
}
}
}
int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
a[u].push_back(make_pair(w,v));
}
// puts("");
dij(1);
// for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
printf("%d\n",dis[n]);
return 0;
}
/*
4 5
1 3 1
2 4 2
1 2 2
3 4 2
2 4 1
*/数列变换
$60pts$ 的送分写法，暴力，按题意模拟出一个 $f$ 递归函数，执行一遍即可。
$100pts$ 的写法：先咕着。
代码
卡牌游戏
代码
舞台表演
代码
