如何创建网站平台的详细步骤,wordpress 文章类,做配电柜在哪个网站发布信息,制作网站费用题干#xff1a;
给你n个点#xff0c;m条无向边#xff0c;每条边都有长度d和花费p#xff0c;给你起点s终点t#xff0c;要求输出起点到终点的最短距离及其花费#xff0c;如果最短距离有多条路线#xff0c;则输出花费最少的。
Input
输入n,m#xff0c;点的编号…题干
给你n个点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时输入结束。 (1n1000, 0m100000, s ! t)
Output
输出 一行有两个数 最短距离及其花费。
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
解题报告 最短路的双权值问题优先级高的满足小于关系的时候对于优先级低的需要无脑加当优先级高的相等的时候优先级较低的才可以取min 。
AC代码
#includebits/stdc.husing namespace std;
const int MAX 1000 5;
const int INF 0x3f3f3f3f;
int cost[MAX],dis[MAX];
bool vis[MAX];
int head[MAX];
int n,m;
int cnt;
int st,ed;
//w代表距离c代表花费
struct Edge {int to,w,ne,c;
} e[100000 5];
struct Point {int pos;int w,c;Point(){}Point(int pos,int w,int c):pos(pos),w(w),c(c){}bool operator(const Point b) const {return wb.w;}
} p;
void Dijkstra(int u,int v) {dis[u] 0;cost[u] 0;int all n,minw INF,minv;priority_queuePoint pq;pq.push(Point(u,0,0));while(!pq.empty()) {
// printf(...\n);Point cur pq.top();pq.pop();
// if(vis[cur.pos] 1) continue;//加不加都可以 vis[cur.pos] 1;if(cur.pos v) break;int x cur.pos;for(int i head[x]; i!-1; ie[i].ne) {
// if(vis[e[i].to] 1) continue; 这句千万不能加。。。 if(dis[e[i].to] dis[x] e[i].w ) {dis[e[i].to] dis[x] e[i].w;cost[e[i].to] cost[x] e[i].c;pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to]));}else if(dis[e[i].to] dis[x] e[i].w) {cost[e[i].to] min(cost[e[i].to] , cost[x] e[i].c);pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to]));}
// if(vis[e[i].to ] 0)
// pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to])); }}printf(%d %d\n,dis[v],cost[v]);
} void add(int a,int b,int w,int c) {e[cnt].to b;e[cnt].w w;e[cnt].c c; e[cnt].ne head[a];head[a] cnt;
}
void init() {cnt 0;memset(head,-1,sizeof(head));memset(dis,INF,sizeof(dis));memset(cost,INF,sizeof(cost));memset(vis,0,sizeof(vis));
}
int main()
{int a,b,d,p;while(~scanf(%d%d,n,m)) {if(n 0 m 0) break;init();while(m--) {scanf(%d%d%d%d,a,b,d,p);add(a,b,d,p);add(b,a,d,p);}scanf(%d%d,st,ed);Dijkstra(st,ed); }return 0 ;
}MLE代码就是push的位置不同就会MLE //改一下push的位置 能过吗
#includebits/stdc.husing namespace std;
const int MAX 1000 5;
const int INF 0x3f3f3f3f;
int cost[MAX],dis[MAX];
bool vis[MAX];
int head[MAX];
int n,m;
int cnt;
int st,ed;
//w代表距离c代表花费
struct Edge {int to,w,ne,c;
} e[100000 5];
struct Point {int pos;int w,c;Point(){}Point(int pos,int w,int c):pos(pos),w(w),c(c){}bool operator(const Point b) const {return wb.w;}
} p;
void Dijkstra(int u,int v) {dis[u] 0;cost[u] 0;int all n,minw INF,minv;priority_queuePoint pq;pq.push(Point(u,0,0));while(!pq.empty()) {
// printf(...\n);Point cur pq.top();pq.pop();
// if(vis[cur.pos] 1) continue;//加不加都可以 vis[cur.pos] 1;if(cur.pos v) break;int x cur.pos;for(int i head[x]; i!-1; ie[i].ne) {
// if(vis[e[i].to] 1) continue; 这句千万不能加。。。 if(dis[e[i].to] dis[x] e[i].w ) {dis[e[i].to] dis[x] e[i].w;cost[e[i].to] cost[x] e[i].c;
// pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to]));}else if(dis[e[i].to] dis[x] e[i].w) {cost[e[i].to] min(cost[e[i].to] , cost[x] e[i].c);
// pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to]));}if(vis[e[i].to ] 0) pq.push(Point(e[i].to,dis[e[i].to],cost[e[i].to])); }}printf(%d %d\n,dis[v],cost[v]);
} void add(int a,int b,int w,int c) {e[cnt].to b;e[cnt].w w;e[cnt].c c; e[cnt].ne head[a];head[a] cnt;
}
void init() {cnt 0;memset(head,-1,sizeof(head));memset(dis,INF,sizeof(dis));memset(cost,INF,sizeof(cost));memset(vis,0,sizeof(vis));
}
int main()
{int a,b,d,p;while(~scanf(%d%d,n,m)) {if(n 0 m 0) break;init();while(m--) {scanf(%d%d%d%d,a,b,d,p);add(a,b,d,p);add(b,a,d,p);}scanf(%d%d,st,ed);Dijkstra(st,ed); }return 0 ;
}
