解決圖論問題，首先就要思考用什么樣的方式存儲圖。但是小鑫卻怎么也弄不明白如何存圖才能有利于解決問題。你能幫他解決這個問題么？ Input 多組輸入，到文件結尾。
每一組第一行有兩個數n、m表示n個點，m條有向邊。接下來有m行，每行兩個數u、v、w代表u到v有一條有向邊權值為w。第m+2行有一個數q代表詢問次數，接下來q行每行有一個詢問，輸入一個數為a
注意：點的編號為0~n-1，2<=n<=500000 ，0<=m<=500000，0<=q<=500000，u!=v，w為int型數據。輸入保證沒有自環和重邊 Output 對于每一條詢問，輸出一行兩個數x，y。表示排序后第a條邊是由x到y的。對于每條邊來說排序規則如下：
權值小的在前。權值相等的邊出發點編號小的在前權值和出發點相等的到達點編號小的在前注：邊的編號自0開始 Example Input
4 3 0 1 1 1 2 2 1 3 0 3 0 1 2
Example Output
1 3 0 1 1 2
排序有點亂的說..
#include <stdio.h>#include <iostream>using namespace std;struct node{ int u,v,w;}head[500005];void qsort(int left,int right){ int i=left,j=right; if(left>=right) return ; int t1=head[left].u,t2=head[left].v,t3=head[left].w; while(i<j) { while(i<j&&((head[j].w>t3)||(head[j].w==t3&&head[j].u>t1)||(head[j].w==t3&&head[j].u==t1&&head[j].v>t2))) j--; head[i]=head[j]; while(i<j&&((head[i].w<t3)||(head[i].w==t3&&head[i].u<t1)||(head[i].w==t3&&head[i].u==t1&&head[i].v<t2))) i++; head[j]=head[i]; } head[i].u=t1; head[i].v=t2; head[i].w=t3; qsort(left,i-1); qsort(i+1,right);}int main(){ int n,m,x,y,a; while(cin>>n>>m) { int i; for(i=0;i<m;i++) { cin>>head[i].u>>head[i].v>>head[i].w; } int q; cin>>q; qsort(0,m-1); while(q--) { cin>>a; printf("%d %d/n",head[a].u,head[a].v); } } return 0;}/***************************************************User name: Result: AcceptedTake time: 252msTake Memory: 548KBSubmit time: 2017-02-20 09:06:09****************************************************/新聞熱點
疑難解答
