网站建设与开发 期末作品,一般公司网站的后台管理在哪,号卡分销系统,网站建设 业务板块名称给你n个点#xff0c;m条无向边#xff0c;每条边都有长度d和花费p#xff0c;给你起点s终点t#xff0c;要求输出起点到终点的最短距离及其花费#xff0c;如果最短距离有多条路线#xff0c;则输出花费最少的。 Input 输入n,m#xff0c;点的编号是1~n,然后是m行m条无向边每条边都有长度d和花费p给你起点s终点t要求输出起点到终点的最短距离及其花费如果最短距离有多条路线则输出花费最少的。 Input 输入n,m点的编号是1~n,然后是m行每行4个数 a,b,d,p表示a和b之间有一条边且其长度为d花费为p。最后一行是两个数 s,t;起点s终点。n和m为0时输入结束。 (1 n 1000, 0 m 100000, s ! t) Output 输出 一行有两个数 最短距离及其花费。 Sample Input 3 2 1 2 5 6 2 3 4 5 1 3 0 0 Sample Output 9 11
分析与解答
这题我调试了八个小时 我总结一下我对dijkstra的认识
1.dijkstra算法可以求从单个源点出发到所有结点的最短路这个题就是坑到这了我写两个参数就wrong answer了就是说你调用这个函数只需要一个参数就是起点。终点是n已经固定了现在你说终点是t哪怕走到终点n的路不经过t你输出dis[t]也是从起点到t的最短路。 每标记一次就说明被标记的这个数的dis已经确定了。我们循环n次目的就是为了标记n次确定n个数的dis。我们初始化起点的dis是0其他的是inf我们循环n次第一个确定下来的就是起点。然后标记注意这个标记是在那n次循环里的。 2.这个题第二个坑就是两个点之间的路有多条如果路的距离相同时还要找花费最小的
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define INF 100100
using namespace std;int vis[1100];int dis[1100];
int map[1100][1100];
int value[1100][1100];
int v[1100];
int n;
void dijkstra(int s){memset(vis,0,sizeof(vis));for(int i1;in;i){dis[i]INF;v[i]INF;}dis[s]v[s]0;for(int i1;in;i){//循环n次每一次都选一个点标记上int x,mINF;for(int y1;yn;y){//所有未标号节点中选dis最小的结点if(!vis[y]dis[y]m)mdis[xy];}vis[x]1;for(int y1;yn;y)//从x出发的所有边x,y),更新dis[y]{ if (dis[y] dis[x] map[x][y]){dis[y] dis[x]map[x][y];v[y] v[x] value[x][y];}else if (dis[y] dis[x] map[x][y] v[y] v[x] value[x][y]){v[y] v[x] value[x][y];}}}
}int main() {int m;int a,b,c,p;int s,t;while(cinnm){if(m0n0) return 0;//// memset(v,INF,sizeof(v));memset(map,INF,sizeof(map));memset(value,INF,sizeof(value));for(int i0;im;i){scanf(%d%d%d%d,a,b,c,p);if(cmap[a][b]){map[a][b]map[b][a]c;value[a][b]value[b][a]p;}if(cmap[a][b]value[a][b]p){value[b][a]value[a][b]p;}}scanf(%d%d,s,t);dijkstra(s);printf(%d %d\n,dis[t],v[t]);}
}
