这道题数据范围小,方法比较多。我用floyd和spfa分别写了一下,spfa明显有时间优势。
一个小技巧在于:把城市名称对应到数字序号,处理是用数字。
方法一:spfa
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<cctype> #include<sstream> using namespace std; #define pii pair<int,int> #define LL long long int const int eps=1e-8; const int INF=1000000000; const int maxn=200+10; int n,r,cas=0,ton,num,used[maxn],d[maxn],m[maxn][maxn]; char city[maxn][33]; char s[33],e[33]; vector<int>v[maxn]; int index(char *ss) { int i; for(i=0;i<num;i++) { if(strcmp(ss,city[i])==0) { return i; } } strcpy(city[num++],ss); return i; } void ini() { num=0; for(int i=0;i<n;i++) { strcpy(city[i],"