给定一个带权有向图G=（V，E），其中每条边的权是一个正整数，另外给定一个顶点v作为源点，求从源点v到其余各顶点的最短路径长度。 请用分枝限界法编程解决之，要求用c++编写完整的程序并进行测试

以下是使用分枝限界法求解单源最短路径的C++代码：

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define MAX 100005
#define INF 0x3f3f3f3f
using namespace std;

int n,m,s;
int head[MAX],cnt;
struct Edge{
    int to,nxt,w;
}edge[MAX];

inline void add_edge(int u,int v,int w){
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}

struct Node{
    int u,dist;
    bool operator < (const Node &A) const{
        return dist>A.dist;
    }
};

priority_queue<Node> q;

int dis[MAX],vis[MAX];

int dijkstra(int s){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));

    dis[s]=0;
    q.push({s,0});

    while(!q.empty()){
        Node x=q.top(); q.pop();
        int u=x.u;

        if(vis[u]) continue;
        vis[u]=1;

        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].w){
                dis[v]=dis[u]+edge[i].w;
                if(!vis[v]) q.push({v,dis[v]});
            }
        }
    }

    return dis[n];
}

struct P{
    int u,dist,depth;
    bool operator < (const P &A) const{
        return dist>A.dist;
    }
};

priority_queue<P> q1;

int ans=INF;

void dfs(int u,int depth,int cost){
    if(u==n) ans=min(ans,cost);
    if(depth==n-1) return;

    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(cost+edge[i].w+(n-depth-1)*dijkstra(v)>=ans) continue;
        q1.push({v,cost+edge[i].w,depth+1});
    }

    while(!q1.empty()){
        P x=q1.top(); q1.pop();
        dfs(x.u,x.depth,x.dist);
    }
}

int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }

    dfs(s,0,0);

    if(ans==INF) cout<<"No solution"<<endl;
    else cout<<ans<<endl;

    return 0;
}

对于该代码的解释如下：

1. 定义了一个Edge结构体来表示图中的一条边；
2. 定义了一个add_edge函数来向邻接表中添加边；
3. 定义了一个Node结构体来表示Dijkstra算法中的节点；
4. 定义了一个优先队列q来存储Dijkstra算法中的节点，并重载了小于运算符，使得队首元素为最小元素；
5. 定义了dis数组来存储源点到各个顶点的最短路径长度，vis数组来标记各个顶点是否已经被访问过；
6. 实现了Dijkstra算法，使用优先队列q来维护优先级；
7. 定义了一个P结构体来表示分枝限界法中的节点；
8. 定义了一个优先队列q1来存储分枝限界法中的节点，并重载了小于运算符，使得队首元素为最小元素；
9. 定义了ans变量来存储最终的结果，初始化为无穷大；
10. 实现了dfs函数，使用优先队列q1来维护优先级，通过比较当前节点到终点的最短路径长度和当前已知的最短路径长度ans来进行剪枝；
11. 在主函数中读入图的信息，调用dfs函数求解结果，并输出结果。

该代码的时间复杂度为$O(nm\log n)$，其中$n$为顶点数，$m$为边数。