品牌营销策划书模板,济南软件优化网站建设,js网站文字重叠,浏览器游戏网址邮递员送信 时间限制: 1 Sec 内存限制: 64 MB提交: 10 解决: 5[提交][状态][讨论版] 题目描述 有一个邮递员要送东西#xff0c;邮局在节点1.他总共要送N-1样东西#xff0c;其目的地分别是2~N。由于这个城市的交通比较繁忙#xff0c;因此所有的道路都是单行的#xff0…邮递员送信 时间限制: 1 Sec 内存限制: 64 MB提交: 10 解决: 5[提交][状态][讨论版] 题目描述 有一个邮递员要送东西邮局在节点1.他总共要送N-1样东西其目的地分别是2~N。由于这个城市的交通比较繁忙因此所有的道路都是单行的共有M条 道路通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。 输入 第一行包括两个整数N和M。 第2到第M1行每行三个数字U、V、W表示从A到B有一条需要W时间的道路。 满足1U,VN,1W10000,输入保证任意两点都能互相到达。 输出 输出仅一行包含一个整数为最少需要的时间。 样例输入 5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2样例输出 83提示 对于30%的数据有1≤N≤200; 对于100%的数据有1≤N≤1000,1≤M≤100000。 【分析】两次SPFA第二次把边全反过来。 #include iostream
#include cstring
#include cstdio
#include cstring
#include algorithm
#include cmath
#include time.h
#include string
#include map
#include stack
#include vector
#include set
#include queue
#define inf 0x3f3f3f3f
#define mod 1000000007
typedef long long ll;
using namespace std;
const int N1005;
const int M100005;
int cost[N][N];
ll d[N],D[N];
int n,m;
ll ans0;
bool vis[N];
void spfa(int s) {int i,j,now;memset(vis,false,sizeof(vis));for(i1; in; i) {d[i]inf;}d[s]0;vis[s]true;queueint q;q.push(s);while(!q.empty()) {nowq.front();q.pop();vis[now]false;for(i1; in; i) {if(d[i]d[now]cost[now][i]) {d[i]d[now]cost[now][i];if(!vis[i]) q.push(i),vis[i]true;}}}for(int i2; in; i)ansd[i];
}
int main() {int i,j,a,b,c;scanf(%d%d,n,m);for(i1; in; i) {for(j1; ji; j) {if(ij) cost[i][j]0;else cost[i][j]cost[j][i]inf;}}for(i0; im; i) {scanf(%d%d%d,a,b,c);cost[a][b]min(cost[a][b],c);}spfa(1);for(i1; in; i)for(ji1; jn; j)swap(cost[i][j],cost[j][i]);spfa(1);coutansendl;return 0;
} View Code 转载于:https://www.cnblogs.com/jianrenfang/p/5827279.html
