1087. Dijkstra + DFS:解决四标尺

其中:第四标尺路径条数也可用num[]数组,放在Dijkstra中

#include<string>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
const int maxn = 200, INF = 1000000000;
int n, m, nump = 0, optvalue = 0, vis[maxn], g[maxn][maxn], d[maxn], w[maxn],
		weight[maxn], num = 0; //编号从0开始
double ave = 0;
map<int, string> int2string;
map<string, int> string2int;
vector<int> pre[maxn], path, temppath;
string start;
void dijkstra(int v) //第一标尺
		{
	int min, u;
	fill(d, d + maxn, INF);
//fill(num,num+maxn,0);
	d[v] = 0;
//num[v]=1;
	for (int i = 0; i < n; i++) {
		min = INF;
		for (int j = 0; j < n; j++) {
			if (vis[j] == 0 && min > d[j]) {
				min = d[j];
				u = j;
			}
		}
		vis[u] = 1;
		for (int k = 0; k < n; k++) {
			if (vis[k] == 0) {
				if (d[k] > d[u] + g[u][k]) {
					d[k] = d[u] + g[u][k];
					pre[k].clear();
					pre[k].push_back(u);
// num[k]=num[u];
				} else if (d[k] == d[u] + g[u][k]) {
					pre[k].push_back(u);
//num[k]+=num[u];
				}
			}
		}
	}
}
void dfs(int st, int ed) {
	if (ed == st) {
		num++; //第四标尺
		temppath.push_back(ed);
		int value = 0;
		for (int i = temppath.size() - 1; i >= 0; i--) {
			int id = temppath[i];
			value += weight[id];
		}
		if (value > optvalue) //第二标尺
				{
			optvalue = value;
			path = temppath;
			ave = value * 1.0 / (temppath.size() - 1);
		} else if (value == optvalue
				&& value * 1.0 / (temppath.size() - 1) > ave) //第三标尺
						{
			ave = value * 1.0 / (temppath.size() - 1);
			path = temppath;
		}
		temppath.pop_back();
		return;
	}
	temppath.push_back(ed);
	for (int i = 0; i < pre[ed].size(); i++)
		dfs(st, pre[ed][i]);
	temppath.pop_back();
}
int change(string str) {
	if (string2int.find(str) != string2int.end())
		return string2int[str];
	else {
		string2int[str] = nump;
		int2string[nump] = str;
		return nump++;
	}
}
int main() {
	cin >> n >> m >> start;
	string str, strr;
	string end = "ROM";
	fill(g[0], g[0] + maxn * maxn, INF);
	int st = change(start);
	int ed = change(end);
	weight[st] = 0;
	for (int i = 0; i < n - 1; i++) {
		cin >> str;
		int id = change(str);
		cin >> weight[id];
	}
	for (int i = 0; i < m; i++) {
		cin >> str >> strr;
		int id1 = change(str);
		int id2 = change(strr);
		cin >> g[id1][id2];
		g[id2][id1] = g[id1][id2];
	}
	dijkstra(st);
	dfs(st, ed);
	cout << num << " " << d[ed] << " " << optvalue << " " << int(ave) << endl;
	for (int i = path.size() - 1; i >= 0; i--) {
		cout << int2string[path[i]];
		if (i > 0)
			cout << "->";
	}
	return 0;
}

 

0

字母字符串和整型编号的映射

第一种方法:哈希变化。(用的太少,比特币挖矿)

第二种方法:map容器;

int num=0;//编号从0开始
map<int,string>int2string;
map<string,int>string2int;
int change(string str)
{
    if(string2int.find(str)!=string2int.end())
        return string2int[str];
    else
    {
        string2int[str]=num;
        int2string[num]=str;
        return num++;
    }
}

 

0

1072. Gas Station (30)-PAT甲级真题(Dijkstra)

 

原题:https://www.patest.cn/contests/pat-a-practise/1072

每次遍历d[],求所有最短路径中最小的;

#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
using namespace std;
const int maxn = 1011, INF = 1000000000;
int n, m, k, ds, g[maxn][maxn], d[maxn], vis[maxn];

int string2int(string str) {
	stringstream ss;
	int a;
	ss << str;
	ss >> a;
	return a;
}
int dijkstra(int v, int &minds, int &add) {
	int min, u;
	fill(vis, vis + maxn, 0);
	fill(d, d + maxn, INF);
	d[v] = 0;
	for (int i = 0; i < n + m; i++) {
		min = INF;
		for (int j = 1; j <= n + m; j++) {
			if (vis[j] == 0 && min > d[j]) {
				min = d[j];
				u = j;
			}
		}
		vis[u] = 1;
		for (int k = 1; k <= n + m; k++) {
			if (vis[k] == 0 && d[k] > d[u] + g[u][k])
				d[k] = d[u] + g[u][k];
		}
	}
for(int i=1;i<=n;i++)/*遍历d[],不能在求d[]的过程中遍历,只能全部求完d[]之后
 {
 if(d[i]>ds)
 return 1;
 add+=d[i];
 if(minds>d[i])
 minds=d[i];
 }
 return -1;
 }
 int main()
 {
 int id1,id2;
 int ansid,ansds=0,ansadd=INF,minds,add;
 cin>>n>>m>>k>>ds;
 fill(g[0],g[0]+maxn*maxn,INF);
 string a,b;
 for(int i=0;i<k;i++)
 {
 cin>>a>>b;
 if(a[0]=='G')
 id1=n+string2int(a.substr(1));
 else
 id1=string2int(a);
 if(b[0]=='G')
 id2=n+string2int(b.substr(1,b.size()-1));
 else
 id2=string2int(b);
 cin>>g[id1][id2];
 g[id2][id1]=g[id1][id2];
 }
 for(int i=1;i<=m;i++)
 {
 minds=INF;
 add=0;
 if(dijkstra(n+i,minds,add)>0)
 continue;
 if(minds>ansds)
 {
 ansds=minds;
 ansid=n+i;
 ansadd=add;
 }
 else if(minds==ansds&&add<ansadd)
 {
 ansid=n+i;
 ansadd=add;
 }
 }
 if(ansadd==INF)
 cout<<"No Solution"<<endl;
 else
 {
 cout<<"G"<<ansid-n<<endl;
 printf("%0.1f %0.1f\n",ansds*1.0,ansadd*1.0/n);
 }
 return 0;
 }

 

0

C++中string与int,double转化

 

注意:保留为浮点数时会有误差,貌似都只能六位有效数字(包括整数)

第一种方法:头文件#include<sstream>,c++98,如果需要转化为long long,返回值前面加上long long即可;与double等浮点数进行转换的时候直接改类型即可。

int stringToint(const string &S)//利用stringstream完成string到int的转换  
{  
    stringstream ss;  
    int result;  
    ss << S; ss >> result;  //string可以为单个字符
    return result;  
}
string intTostring(const int &a)//利用stringstream完成int到string的转换
{
	stringstream  ss;
	string str;
	ss<<a; ss>>str;
	return str;
}

第二种方法:c++11[hermit auto=”1″ loop=”0″ unexpand=”0″

①string to others:String中函数stoi(Convert string to integer),stoll(Convert string to long long),Stod(Convert string to double),stof(Convert string to float)

②others to string:to_string(int val)

 

0