头像

yan6


访客:76

在线 



yan6
6天前

题目描述

Dijkstra求最短路 II


算法1

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;

typedef pair<int,int> PII;

const int N=2e5+10;

int n;
int m;

int h[N];//邻接表存储稀疏图
int e[N];
int ne[N];
int w[N];
int idx;


bool st[N];
int dis[N];


void add(int a,int b,int c)
{
    e[idx]=b;//e[坐标]=点
    w[idx]=c;//w[坐标]=c

    ne[idx]=h[a];//ne[idx]的下一个坐标是什么坐标
    h[a]=idx;//h[点]=坐标
    idx++;
}

int dijkstra()//堆优化堆Dijkstra
{
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;

    priority_queue<PII,vector<PII>,greater<>> heap;
    heap.push({0,1});

    while(heap.size())
    {

        auto t=heap.top();
        heap.pop();

        int distance=t.first;
        int v=t.second;

        if(st[v]) continue;

        st[v]=true;

        for(int i=h[v];i!=-1;i=ne[i])
        {
            int j=e[i];//j是点,i是坐标

            if(dis[j] > distance +w[i])
            {
                dis[j]=distance + w[i];
                heap.push({dis[j],j});
            }
        }
    }

    if(dis[n]==0x3f3f3f3f) return -1;

    return dis[n];

}

int  main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);

    }

    int res=dijkstra();

    printf("%d\n",res);

    return 0;
}






yan6
7天前

题目描述

Dijkstra求最短路 I

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510;

int n;
int m;

int g[N][N];
int dis[N];//1到每个点到距离
bool st[N];

int dijkstra()//Dijkstra求单源最短路
{
    memset(dis,0x3f,sizeof(dis));//先距离设为无穷,1号点到自身距离为0
    dis[1]=0;

    for(int i=0;i<n;++i)//n次循环,只是循环n次,i无意义
    {
        int t=-1;

        for(int j=1;j<=n;++j)//看看哪个点不再集合,并且通过该点可以距离更小
        {
            if(!st[j] && (t==-1 || dis[t]>dis[j]))//在所有st为false的点中找到距离最小的点
            {
                t=j;
            }
        }

        st[t]=true;//把j加入集合

        for(int j=1;j<=n;++j)
        {
            dis[j]=min(dis[j],dis[t]+g[t][j]);//如果经过t到j,距离更小就更新距离
        }
    }

    if(dis[n]==0x3f3f3f3f) return -1;// 如果1号到n号的距离为无穷,返回-1

    return dis[n];
}

int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof(g));


    while(m--)
    {
        int a;
        int b;
        int c;

        cin>>a>>b>>c;

        g[a][b]=min(g[a][b],c);
    }

    cout<< dijkstra()<<endl;

    return 0;
}







yan6
11天前

题目描述

n皇后


算法1

C++ 代码

#include<iostream>

using namespace std;

const int N=20;
char g[N][N];

int n;
bool row[N];
bool col[N];
bool dg[N];
bool udg[N];

void dfs(int x,int y,int s)//从左到右,每一行一个个开始遍历
{
    if(y==n)
    {
        y=0;
        ++x;
    }

    if(x==n)//坐标从0开始,搜到第n行结束
    {
        if(s==n)
        {
            for(int i=0;i<n;++i) puts(g[i]);
            puts("");//输出每行后,加换行

        }

        return ;//放在if外面
    }

    //不放
    dfs(x,y+1,s);

    //

    if(!col[y] && !row[x] && !dg[x+y] && !udg[x-y+n] )//坐标和,坐标差相等,数组下标为正数,所以加n
    {
        g[x][y]='Q';
        col[y]=row[x]=dg[x+y]=udg[x-y+n]=true;
        dfs(x,y+1,s+1);

        col[y]=row[x]=dg[x+y]=udg[x-y+n]=false;
        g[x][y]='.';
    }
}


int main()
{
    cin>>n;

    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            g[i][j]='.';
        }
    }

    dfs(0,0,0);

    return 0;
}