头像

马扎特




离线:1小时前


活动打卡代码 AcWing 1126. 最小花费

马扎特
1小时前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define ll long long int
const int MAXN = 2000 + 10;
const int MAXM = 2e5+10;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int NINF=-INF-1;
const ll mod=1e9+7;
#define PI acos(-1.0)
ll n,m;
ll head[MAXN],tot;
double dist[MAXN];
bool vis[MAXN];
struct Edge{
    ll next,to,dat;
}edge[MAXM];
void add(ll x,ll y,ll c)
{
    edge[tot].to=y;
    edge[tot].dat=c;
    edge[tot].next=head[x];
    head[x]=tot++;
}
typedef pair<double,ll> PII;
void dijkstra(ll st) {
     for(int i = 0;i<n;i++)dist[i+1] = -1e9;
    memset(vis,0,sizeof(vis));

   priority_queue<PII,vector<PII>,less<PII> > q;
    while(!q.empty()) q.pop();
    dist[st]=1;
    q.push(make_pair(1.0,st));
    while(!q.empty()) {
        ll x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(ll i=head[x]; i !=-1; i=edge[i].next) {
            ll y=edge[i].to;
            double w=(1-0.01*edge[i].dat);

            if(dist[y]<dist[x]*w) {
                dist[y]=dist[x]*w;
                q.push(make_pair(dist[y],y));
              //  path[y]=x;
            }
        }
    }
}
ll st,en;
int main(){
scanf("%lld%lld",&n,&m);
    memset(head,-1,sizeof(head));
    for(ll i=0;i<m;i++)
    {
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        add(a,b,c),add(b,a,c);

    }
    scanf("%lld%lld",&st,&en);
    dijkstra(st);


    printf("%.8lf\n",100/dist[en]);

    return 0;   
}




活动打卡代码 AcWing 1127. 香甜的黄油

马扎特
1小时前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define ll long long int
const int MAXN = 800 + 10;
const int MAXM = 2900+10;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int NINF=-INF-1;
const ll mod=1e9+7;
#define PI acos(-1.0)
ll n,p,c;
ll a[MAXN],d[MAXN][MAXN];
ll head[MAXN],tot;
bool vis[MAXN];
struct Edge{
    ll next,to,dat;
}edge[MAXM];
void add(ll x,ll y,ll c)
{
    edge[tot].to=y;
    edge[tot].dat=c;
    edge[tot].next=head[x];
    head[x]=tot++;
}
void spfa(ll st,ll dist[]){
    memset(vis,false,sizeof(vis));
    queue<ll> q;
    q.push(st);
    vis[st]=true;
    dist[st]=0;
    while(q.size())
    {   ll x=q.front();
        q.pop();
        vis[x]=false;
        for(ll i=head[x];~i;i=edge[i].next)
        {   ll y=edge[i].to,w=edge[i].dat;
            if(dist[y]>dist[x]+w)
            {
                dist[y]=dist[x]+w;
                if(!vis[y])
                {   q.push(y);
                    vis[y]=true;

                }
            }


        }

    }

}
int main(){
    scanf("%lld%lld%lld",&n,&p,&c);    
    memset(head,-1,sizeof(head));
    memset(d,0x3f,sizeof(d));
    tot=0;
    for(ll i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    for(ll i=0;i<c;i++)
    {   ll a,b,c;
      scanf("%lld%lld%lld",&a,&b,&c);
        add(a,b,c),add(b,a,c);  
    }
    for(ll i=1;i<=n;i++)
    spfa(a[i],d[i]);

    ll ans=LINF;
     for(ll i=1;i<=p;i++)
      {     ll res=0;
         for(ll j=1;j<=n;j++)
            {   if(res<LINF)
                res+=d[j][i];

            }


        ans=min(ans,res);

      }
      cout<<ans<<endl;


    return 0;   
}




活动打卡代码 AcWing 1128. 信使

马扎特
12小时前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define ll long long int
const int MAXN = 100 + 10;
const int MAXM = 400+10;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int NINF=-INF-1;
const ll mod=1e9+7;
#define PI acos(-1.0)
ll n,m;
ll head[MAXN],tot,dist[MAXN],vis[MAXN];
typedef pair<ll,ll> PII;
struct Edge{
    ll next,to,dat;

}edge[MAXM];
void add(ll x,ll y,ll c)
{   edge[tot].to=y;
    edge[tot].dat=c;
    edge[tot].next=head[x];
    head[x]=tot++;

}
void dijkstra(ll st)
{   memset(dist,0x3f,sizeof(dist));
    memset(vis,false,sizeof(vis));
    dist[st]=0;
    priority_queue<PII,vector<PII>, greater<PII> >q;
    q.push({0,st});
    while(q.size())
    {   ll x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(ll i=head[x];~i;i=edge[i].next)
        {   ll j=edge[i].to,w=edge[i].dat;
            if(dist[j]>dist[x]+w)
            {   dist[j]=dist[x]+w;
                q.push({dist[j],j});

            }


        }

    }


}
int main(){
   scanf("%lld%lld",&n,&m);
   memset(head,-1,sizeof(head));
   while(m--)
   {    ll a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    add(a,b,c),add(b,a,c);


   }
  dijkstra(1);
    ll ans=0;
    for(ll i=1;i<=n;i++)
    ans=max(ans,dist[i]);
    if(ans==LINF) ans=-1;
    cout<<ans<<endl;

    return 0;
}




活动打卡代码 AcWing 1129. 热浪

马扎特
12小时前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define ll long long int
const int MAXN = 2500 + 10;
const int MAXM = 6200*2+10;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int NINF=-INF-1;
const ll mod=1e9+7;
#define PI acos(-1.0)
ll n,m,s,t;
ll head[MAXN],tot,dist[MAXN],vis[MAXN];
typedef pair<ll,ll> PII;
struct Edge{
    ll next,to,dat;

}edge[MAXM];
void add(ll x,ll y,ll c)
{   edge[tot].to=y;
    edge[tot].dat=c;
    edge[tot].next=head[x];
    head[x]=tot++;

}
ll dijkstra(ll st)
{   memset(dist,0x3f,sizeof(dist));
    memset(vis,false,sizeof(vis));
    dist[st]=0;
    priority_queue<PII,vector<PII>, greater<PII> >q;
    q.push({0,st});
    while(q.size())
    {   ll x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(ll i=head[x];~i;i=edge[i].next)
        {   ll j=edge[i].to,w=edge[i].dat;
            if(dist[j]>dist[x]+w)
            {   dist[j]=dist[x]+w;
                q.push({dist[j],j});

            }


        }

    }
    return dist[t];

}
int main(){
   scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    memset(head,-1,sizeof(head));
   while(m--)
   {    ll a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    add(a,b,c),add(b,a,c);


   }
   printf("%lld\n",dijkstra(s));

    return 0;
}




活动打卡代码 AcWing 1142. 繁忙的都市

马扎特
12小时前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long int
const int MAXN = 300+ 10;
const int MAXM = 8100;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int NINF=-INF-1;
const ll mod=1e9+7;
#define PI acos(-1.0)
ll n,m;
struct Edge{
ll u,v,w;
    bool operator < (const Edge &other) const{
        return w<other.w;
    }
}edge[MAXM];
ll pre[MAXN];
ll find(ll x){
    return pre[x]==x?x:pre[x]=find(pre[x]);
}
int main(){
   cin>>n>>m;
   for(int i=0;i<=n;i++) pre[i]=i;
   for(int i=0;i<m;i++)
   cin>>edge[i].u>>edge[i].v>>edge[i].w;
   sort(edge,edge+m);
   int cnt=0;
   int ans;
   for(int i=0;i<m;i++)
   {    int a=find(edge[i].u),b=find(edge[i].v);
        if(a!=b)
        {   pre[a]=b;
            cnt++;

        }
        if(cnt==n-1)
        {   ans=edge[i].w;
            break;

        }


   }
    cout<<cnt<<" "<<ans<<endl;


    return 0;
}




活动打卡代码 AcWing 1140. 最短网络

马扎特
12小时前
#include <bits/stdc++.h>
using namespace std;
const int MAXN =110;
#define ll long long int
const ll LINF = 0x3f3f3f3f3f3f3f3f;
ll g[110][110],n;
ll dist[MAXN];
ll lowcost[MAXN];
ll closest[MAXN];
int Prim(ll v)
{   ll ans=0;
    //closest[i]表示与i点相连的前一个点是XX。
    ll i,j,k,mind;
    for(i=1;i<=n;i++)
    { lowcost[i]=g[v][i];
        closest[i]=v;
    }
    lowcost[v]=0; //之前忽略的点,自己模拟运算过程,找出来的错误。
    for(i=1;i<n;i++)        //输出n-1条边
    { mind=LINF;
        for(j=1;j<=n;j++)
        if(lowcost[j]!=0&&lowcost[j]<mind)
        {  mind=lowcost[j];
            k=j;   //   K记录最近点编号,即刚加入U的顶点。
        }
         //一轮j循环结束后,执行这两行语句
         if(lowcost[k]==LINF) return -1;
         ans+=lowcost[k];

         lowcost[k]=0;                         //lowcost[k]置为0,表示将K点加入U集合

      for(j=1;j<=n;j++) //修改数组lowcost和closest的值
          if(lowcost[j]!=0&&g[k][j]<lowcost[j])   //u-v集合里的边到u集合里的最小值
         {   lowcost[j]=g[k][j];
             closest[j]=k;}
    }
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        cin>>g[i][j];
    cout<<Prim(1)<<endl;

    return 0;
}


活动打卡代码 AcWing 1137. 选择最佳线路

马扎特
12小时前
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000+10;
const int MAXM = 20000 +10;
int head[MAXN],tot,n,m,s;
struct Edge{
    int next,to,dat;
}edge[MAXM];
void add(int x,int y,int c){
    edge[tot].to=y;
    edge[tot].dat=c;
    edge[tot].next=head[x];
    head[x]=tot++;
}
int a[MAXN],w,dist[MAXN];
bool vis[MAXN];
typedef pair<int,int> PII;
void dijkstra(int st)
{   memset(dist,0x3f,sizeof(dist));
    memset(vis,false,sizeof(vis));
    priority_queue<PII,vector<PII>,greater<PII> >q;
    q.push({0,st});
    dist[st]=0;
    while(!q.empty())
    {   int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(int i=head[x];~i;i=edge[i].next)
        {   int j=edge[i].to,w=edge[i].dat;
            if(dist[x]+w<dist[j])
            {   dist[j]=dist[x]+w;
                q.push({dist[j],j});

            }

        }


    }

}

int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n>>m>>s)
    {   memset(head,-1,sizeof(head));
        tot=0;
        while(m--)
        {   int a,b,c;
            cin>>a>>b>>c;
            add(b,a,c);
        }
        cin>>w;
        for(int i=0;i<w;i++)
            cin>>a[i];
        dijkstra(s);
        int ans=0x3f3f3f3f;
        for(int i=0;i<w;i++)
        {   ans=min(ans,dist[a[i]]);
        }
        int ss=-1;
        if(ans==0x3f3f3f3f) cout<<ss<<endl;
        else cout<<ans<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1106. 山峰和山谷

#include <bits/stdc++.h>
const int MAXN = 1010;
using namespace std;
int n;
int h[MAXN][MAXN];
bool higher,lower;
typedef pair<int,int> PII;
bool mark[MAXN][MAXN];
void bfs(int i,int j)
{   queue<PII> q;
    q.push({i,j});
    while(!q.empty())
    {   PII t=q.front();
        q.pop();
        int x=t.first,y=t.second;
        if(mark[x][y]) continue;
        mark[x][y]=true;
        for(int i=x-1;i<=x+1;i++)
        for(int j=y-1;j<=y+1;j++)
        {   if(i<0||i>=n||j<0||j>=n) continue;
            if(x==i&&y==j) continue;
            if(h[x][y]!=h[i][j])
            {   if(h[x][y]>h[i][j]) higher=true;
                else lower=true;
            }
            else q.push({i,j});


        }



    }    

}
int hh,p;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    scanf("%d",&h[i][j]);

     for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {   if(!mark[i][j])
        {   higher=lower=false;
            bfs(i,j);
            if(!higher) p++;
            if(!lower) hh++;

        }


    }
    cout<<hh<<" "<<p<<endl;



    return 0;
}


活动打卡代码 AcWing 1098. 城堡问题

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
#define ll long long int
ll g[MAXN][MAXN];
bool mark[MAXN][MAXN];
ll tot,mm,cnt;
ll n,m;
void dfs(ll x,ll y)
{       mark[x][y]=true;
        cnt++;
       int state=g[x][y],dx,dy;
        if(!(state>>0&1))
        {   dx=x,dy=y-1;
            if(!mark[dx][dy])
               dfs(dx,dy);

        }
        if(!(state>>1&1))
        {   dx=x-1,dy=y;
             if(!mark[dx][dy])
              dfs(dx,dy);

        }
        if(!(state>>2&1))
        {   dx=x,dy=y+1;
            if(!mark[dx][dy])
               dfs(dx,dy);

        }
        if(!(state>>3&1))
        {   dx=x+1,dy=y;
            if(!mark[dx][dy])
               dfs(dx,dy);
        }

    return;
}
int main(){

    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
    for(ll j=1;j<=m;j++)
    scanf("%lld",&g[i][j]);

    for(ll i=1;i<=n;i++)
    for(ll j=1;j<=m;j++)
    if(!mark[i][j])
    {  
        dfs(i,j);
        mm=max(mm,cnt);
        cnt=0;
        tot++;
    }

    cout<<tot<<endl<<mm<<endl;
    return 0;
}


活动打卡代码 AcWing 1250. 格子游戏

#include <bits/stdc++.h>
const int MAXN = 40000+10;
using namespace std;
int pre[MAXN],n,m;
int get(int x,int y)
{
    return (x-1)*n+y;
}
int find(int x)
{
    return pre[x]==x?x:pre[x]=find(pre[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n*n+10;i++)
    pre[i]=i;
    int ans=0;
    bool flag=true;
    for(int i=1;i<=m;i++)
    {   int x,y;
        scanf("%d%d",&x,&y);
        char c;
        cin>>c;

        int a=get(x,y),b;
        if(c=='D') b=get(x+1,y);
        else b=get(x,y+1);
        int fa=find(a),fb=find(b);
        if(fa==fb&&flag)
        {
            ans=i;
            flag=false;
        }
        else{
            pre[fa]=fb;

        }

    }
    if(ans!=0)
    printf("%d\n",ans);
    else puts("draw");
    return 0;
}