843. N皇后
按行枚举
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool cols[N];
bool dg[N];
bool udg[N];
void dfs(int x)
{
if (x == n){
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
return;
}
else{
//对角线y = x + b; b = y - x 可能是负数,所以加个n(往y正轴平移n)
//反对角线y = -x + b; 用截距b来表示这一行上这个点 b = y + x
//这里每一行i,所以i是y轴
//每个列u(横坐标),所以u是x轴
for (int y = 0; y < n; y ++ )
{
if (!cols[y] &&!dg[n + y - x] && !udg[x + y])
{
g[x][y] = 'Q';
cols[y] = dg[n + y - x] = udg[x + y] = 1;
//反对角线
dfs(x + 1);
cols[y] = dg[n + y - x] = udg[x + y] = 0;
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);
return 0;
}
- Dijkstra 朴素
const int N = 511;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1; //一开始初始化为-1。【t存储当前访问的点】
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
//如果是未确定最短距离的点,以及t是初始值或t距离大于j (当前t不是最短的,j是)
//【寻找还未确定最短路的点中路径最短的点】
t = j; //t选为路径更短的点j. 直到遍历完所有点。
//t即是与1号点距离最短的点。
//把t加入s集合中
st[t] = true;
//然后再用这个点去更新剩余点到该点的距离(相邻的点路径值)
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]); //用1--t--x来更新1---x的长度
}
if (dist[n] == 0x3f3f3f3f) return -1; //不连通
return dist[n];
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g); //初始化图,因为最短路问题所以初始化为+无穷
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c); //最短的重边即可
}
int res = dijkstra();
printf("%d", res);
return 0;
}
堆优化
#include <queue>
const int N = 1e6 + 10;
typedef pair<int, int> PII;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist); //初始化正无穷
dist[1] = 0; //定义起点路径距离为0
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); //一①号点,距离是0,编号是1
while (heap.size()) //当堆不是空时
{
// 每次取出当前最小的点 //
auto t = heap.top(); //找到当前距离最小的点 //小根堆,堆顶即是
heap.pop();
int ver = t.second, distance = t.first; //ver表示当前点的编号
if (st[ver]) continue; //如果已经出现过,则这个点是冗余备份,直接跳过即可
st[ver] = true;
// (一共m次)
for (int i = h[ver]; i != -1; i = ne[i]) //注意邻接表的含义。h[ver]以ver编号为起点的相邻的节点链,i不是-1即没到尾节点,就走到下一个点
{
int j = e[i]; //当前值
if (dist[j] > distance + w[i]) //如果当前距离大于经过t到i的距离的话,就更新(选经过t的这条更短的路)
{
dist[j] = distance + w[i];
heap.push({dist[j], j}); //然后把j放入堆里
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[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 t = dijkstra();
printf("%d\n", t);
return 0;
}