图

Dijkstra's algorithm

迪科斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题。

Dij算法c++实现 复杂度O(V²)

// 邻接矩阵
typedef struct _graph
{
    char vexs[MAX];       // 顶点集合
    int vexnum;           // 顶点数
    int edgnum;           // 边数
    int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;


int mp[maxn][maxn]; //邻接矩阵
int dis[maxn];      //起始点到第i点的最短距离
bool visit[maxn];
int n,m;            //顶点数，边数
    void Dijkstra( int s )
    {
        int i,v,u;
        for( i=1; i<=n; ++i ) //初始化
        {
            visit[i]=false;
            dis[i]=mp[1][i];
        }
      dis[s]=0;
      while( true )
      {
            v=-1;
            for( u=1; u<=n; ++u )
                if( !visit[u] && ( v==-1 || dis[u]<dis[v]) )
                    v=u;
            if( v==-1 ) break; 
            visit[v]=true;  //v是最近的顶点

            for( u=1; u<=n; u++ )
                dis[u]= min( dis[u],dis[v]+mp[v][u] );  //动态规划，直接到u点或者先到最近的v点再到u点
    }
}

堆优化

PAT(A) 1003 给定两点的最小路径数

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <list>
#include <stack>
#include <unordered_map>
#include <set>
#include <queue>
#include <climits>
using namespace std;

int weight[501],visit[501];
int map1[501][501];
int mind,cnt,maxt;    //最小距离，最短路径个数，最大权值


void init(int n){
    int i,j;
    for(int i=0;i<n;i++){
        visit[i]=0;
        for(int j=0;j<n;j++){
            map1[i][j]=INT_MAX;
        }
    }
}



void dfs(int s,int e,int dist, int wei,int n)
{
    if(s==e){
        if(dist<mind){ //如果当前路径小于记录的最小路径，更新
            cnt=1;
            mind=dist;
            maxt=wei;
        }
        else if (dist==mind){ //当前路径等于最小路径
            cnt++;
            maxt=max(maxt,wei);
        }
        return;
    }
    
    int i;
    
    if(dist>mind) return;
    
    for(i=0;i<n;i++){  //dfs
        if(visit[i]==0 && map1[s][i]!=INT_MAX){
            visit[i]=1;
            dfs(i,e,dist+map1[s][i],wei+weight[i],n);
            visit[i]=0;
        }
    }
    
}


int main() {
    int n,m,c1,c2;
    mind=INT_MAX;
    cnt=0; 
        
    scanf("%d %d %d %d",&n, &m, &c1, &c2);
    for(int i=0;i<n;++i){
        scanf("%d",&weight[i]);
    }
    init(n);
    int x,y,d;
    while(m--){
        scanf("%d %d %d", &x,&y,&d);
        if(map1[x][y]>d){
            map1[x][y]=map1[y][x]=d;
        }
    }
    dfs(c1,c2,0,weight[c1],n);
    
    cout<<cnt<<" "<<maxt;
    
    
    return 0;
}

BFS

1094. The Largest Generation (25)

#include <cstdio>
#include <queue>

struct Person{
    int id;
    int children[100]; //记录其child的ID
    int child_count; //有几个child
    int generation; //此人属于第几代
    Person():id(0), child_count(0), generation(0){}
};

int main(){
    int M, N;
    int counts[101] = {0}; //用来记录每一代分别有多少人
    scanf("%d%d", &N, &M);
    Person persons[101];

    for(int i = 0;i < M; i++){
        int id, count;
        scanf("%d%d", &id, &count);
        persons[id].id = id;
        persons[id].child_count = count;
        for(int j = 0; j < count; j++){
            scanf("%d", &(persons[id].children[j]));
        }
    }
    //此前的代码都是输入信息

    std::queue<int> q; //q用来决定遍历的顺序
    q.push(01);
    persons[01].generation = 1;
    while(!q.empty()){
        int parent = q.front();
        counts[persons[parent].generation] ++; //这一代又多了一个人
        q.pop();
        for(int i = 0; i < persons[parent].child_count; i++){
            int child = persons[parent].children[i]; //把它的子女放入queue
            q.push(child);
            persons[child].generation = persons[parent].generation + 1; //child的代数 = parent的代数+1
        }
    }
    int max = 0, index = 1;
    for(int i = 1; i < 101; i++){
        if(counts[i] > max){
            max = counts[i];
            index = i;
        }
    }
    printf("%d %d\n", max, index);
    return 0;
}