一点点变形
#include<iostream>
#include<string>
#include<string.h>
#include<vector>
#include<stdio.h>
#include <queue>
#include<algorithm>
using namespace std;
const int maxn=105;
struct Edge
{
int u;
int v;
int dis;
Edge(int a,int b,int c):u(a),v(b),dis(c){}
};
vector<Edge>G[maxn];
int inq[maxn],d[maxn],yi[maxn],flag[maxn];
void init()
{
for(int i=0;i<maxn;i++)G[i].clear();
for(int i=0;i<maxn;i++)d[i]=1e9;
for(int i=0;i<maxn;i++)inq[i]=0;
for(int i=0;i<maxn;i++)flag[i]=0;
}
void spfa(int s,int n)
{
queue<int>q;
q.push(s);inq[s]=1;d[s]=0;
while(!q.empty())
{
int now=q.front();
q.pop(),inq[now]=0;
//遍历所有边
for(int i=0;i<G[now].size();i++)
{
int v=G[now][i].v;
flag[now]+=abs(yi[now]-yi[v]);
if(flag[now]>1)
{
flag[now]--;
continue;
}
//松弛操作
if(d[v]>d[now]+G[now][i].dis)
{
d[v]=d[now]+G[now][i].dis;
if(inq[v]...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
这个方法不太对吧？
比如数据：
3
3
1 2 200
1 3 5
2 3 10
1 2 2
路线应该是1->3->2，花费的最少时间为15，而你这种方法的路线是直接1->2，花费了200的时间。。