127. 单词接龙 最短路或bfs双向bfs（待补题）

127. 单词接龙

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

输出: 5

解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。

示例 2:

输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]

输出: 0

解释: endWord “cog” 不在字典中，所以无法进行转换。

---

解法一 : O ( N 2 ) O(N^2) O(N2)建图，dijkstra跑最短路 压 线 A C \color{red}{压线AC} 压线AC

// #define debug
#ifdef debug
#include <time.h>
#endif

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \
	do { \
	   cout << "\033[31;1m " << #x << " -> "; \
	   err(x); \
	} while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
	   inline void read(T &x, T2 &... oth) {
		   x = 0;
		   char ch = getchar();
		   ll f = 1;
		   while (!isdigit(ch)) {
			   if (ch == '-') f *= -1; 
			   ch = getchar();
		   }
		   while (isdigit(ch)) {
			   x = x * 10 + ch - 48;
			   ch = getchar();
		   }
		   x *= f;
		   read(oth...);
	   }
	template <typename T, typename... T2>
	   inline void print(T x, T2... oth) {
		   ll p3=-1;
		   if(x<0) putchar('-'), x=-x;
		   do{
				print_f[++p3] = x%10 + 48;
		   } while(x/=10);
		   while(p3>=0) putchar(print_f[p3--]);
		   putchar(' ');
		   print(oth...);
	   }
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int tot, n, d[MAXN], vis[MAXN];
string str[MAXN];
unordered_map<string, int> mp;

int ID(string& x) {
	int& rx = mp[x];
	if(!rx) rx = ++ tot, str[tot] = x;
	return rx;
}

struct Edge {
	int v, w;
} ;
vector<Edge> G[MAXN];

class Solution {
public:

	void conn(string& x, string& y) {
		int cnt = 0;
		for(int i=0; i<x.length(); i++)
			cnt += (x[i] != y[i]);
		if(cnt != 1) return ;
		int u = ID(x), v = ID(y);
		G[u].push_back({v, 1});
		G[v].push_back({u, 1});
	}

	void build(string& S, vector<string>& list) {
		for(int i=0; i<=n; i++) G[i].clear();
		for(int i=0; i<list.size(); i++)
			for(int j=i+1; j<list.size(); j++) {
				if(i == j) continue ;
				conn(list[i], list[j]);
			}
		for(int i=0; i<list.size(); i++) 
			conn(list[i], S);
	}

    int ladderLength(string S, string E, vector<string>& list) {
        tot = 0; mp.clear();
		for(auto& it : list) ID(it);
		ID(S);
		int now_tot = tot;
		if(now_tot < ID(E)) return 0;
		n = tot;
		build(S, list);
		return dij(S, E);
	}

	int pre[MAXN];
	int dij(string& S, string& E) {
		int s = ID(S), e = ID(E);
		memset(d, INF, sizeof(d));
		memset(vis, false, sizeof(vis));
		vis[s] = true; d[s] = 0;
		priority_queue<pair<int,int> > q;
		q.push({0, s});
		pre[s] = s;
		while(!q.empty()) {
			auto now = q.top();
			q.pop();
			
			int u = now.second;
			for(auto ed : G[u]) {
				int td = ed.w, v = ed.v;
				if(d[v] > d[u]+td) {
					pre[v] = u;
					d[v] = d[u] + td;
					q.push({-d[v], v});
				} 
			} 
		}
#if 0
        for(int i=1; i<=tot; i++) printf("[%s=%d] ", str[i].data(), d[i]);
        printf("\n");
        for(int i=1; i<=tot; i++) {
            printf("%s: ", str[i].data());
            for(int j=0; j<G[i].size(); j++)
                printf("->%s ", str[G[i][j].v].data());
            printf("\n");
        }
        printf("\n");
		int ts = s, te = e;
		if(d[e] != INF) 
			while(ts != te) {
				printf("%s=>", str[te].data());
				te = pre[te];
			}
		printf("\n");
#endif
		return d[e]==INF ? 0 : d[e]+1;
	}
};

#ifdef debug
signed main() {




   return 0;
}
#endif