AcWing 4243. 传递信息（单源最短路）

题目连接

https://www.acwing.com/problem/content/description/4246/

http://poj.org/problem?id=1502

思路

没啥好说的就是一个裸的求单源最短路，只不过边的信息建立需要自己判断是否存在，范围在100以内，那么基本上所有的最短路都能过，我这里就给出迪杰斯特拉和Floyd的代码

代码 迪杰斯特拉

#include
#include
#include
#include
#include
#include
using namespace std;
#define PII pair
const int INF = 0x3f3f3f3f;
const int N = 1e2+10;

int n,dis[N];
bool vis[N];

struct Node{
	int v,w;
};
vector E[N];

int toint(string s){
	int res = 0;
	for(int i = 0,l = s.size();i n;
	string num;
	for(int i = 2;i num;
			if(num != "x"){
				int w = toint(num);
				E[i].push_back({j,w});
				E[j].push_back({i,w});
			}
		}
	DJ(1);
	int ans = 0;
	for(int i = 1;i